<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span id="local-6989586621679172299"><span id="local-6989586621679172300"></span></span><span class="hs-pragma">{-# LANGUAGE PatternGuards #-}</span><span>
</span><span id="line-2"></span><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span class="hs-cpp">
#if __GLASGOW_HASKELL__
</span><span class="hs-pragma">{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}</span><span>
</span><span id="line-5"></span><span class="hs-pragma">{-# LANGUAGE DeriveGeneric #-}</span><span>
</span><span id="line-6"></span><span class="hs-pragma">{-# LANGUAGE Trustworthy #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#include &quot;containers.h&quot;
</span><span>
</span><span id="line-11"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-12"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-13"></span><span class="hs-comment">-- Module      :  Data.Tree</span><span>
</span><span id="line-14"></span><span class="hs-comment">-- Copyright   :  (c) The University of Glasgow 2002</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- License     :  BSD-style (see the file libraries/base/LICENSE)</span><span>
</span><span id="line-16"></span><span class="hs-comment">--</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-18"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-19"></span><span class="hs-comment">--</span><span>
</span><span id="line-20"></span><span class="hs-comment">-- = Multi-way Trees and Forests</span><span>
</span><span id="line-21"></span><span class="hs-comment">--</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- The @'Tree' a@ type represents a lazy, possibly infinite, multi-way tree</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- (also known as a /rose tree/).</span><span>
</span><span id="line-24"></span><span class="hs-comment">--</span><span>
</span><span id="line-25"></span><span class="hs-comment">-- The @'Forest' a@ type represents a forest of @'Tree' a@s.</span><span>
</span><span id="line-26"></span><span class="hs-comment">--</span><span>
</span><span id="line-27"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-28"></span><span>
</span><span id="line-29"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.Tree</span><span class="hs-special">(</span><span>
</span><span id="line-30"></span><span>
</span><span id="line-31"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Trees and Forests</span></span><span>
</span><span id="line-32"></span><span>      </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier">Tree</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>
</span><span id="line-33"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#Forest"><span class="hs-identifier">Forest</span></a></span><span>
</span><span id="line-34"></span><span>
</span><span id="line-35"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Construction</span></span><span>
</span><span id="line-36"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldTree"><span class="hs-identifier">unfoldTree</span></a></span><span>
</span><span id="line-37"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldForest"><span class="hs-identifier">unfoldForest</span></a></span><span>
</span><span id="line-38"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldTreeM"><span class="hs-identifier">unfoldTreeM</span></a></span><span>
</span><span id="line-39"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldForestM"><span class="hs-identifier">unfoldForestM</span></a></span><span>
</span><span id="line-40"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldTreeM_BF"><span class="hs-identifier">unfoldTreeM_BF</span></a></span><span>
</span><span id="line-41"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#unfoldForestM_BF"><span class="hs-identifier">unfoldForestM_BF</span></a></span><span>
</span><span id="line-42"></span><span>
</span><span id="line-43"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Elimination</span></span><span>
</span><span id="line-44"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#foldTree"><span class="hs-identifier">foldTree</span></a></span><span>
</span><span id="line-45"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#flatten"><span class="hs-identifier">flatten</span></a></span><span>
</span><span id="line-46"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#levels"><span class="hs-identifier">levels</span></a></span><span>
</span><span id="line-47"></span><span>
</span><span id="line-48"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Ascii Drawings</span></span><span>
</span><span id="line-49"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#drawTree"><span class="hs-identifier">drawTree</span></a></span><span>
</span><span id="line-50"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Tree.html#drawForest"><span class="hs-identifier">drawForest</span></a></span><span>
</span><span id="line-51"></span><span>
</span><span id="line-52"></span><span>    </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span class="hs-cpp">

#if MIN_VERSION_base(4,8,0)
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#"><span class="hs-identifier">Data.Foldable</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Foldable.html#toList"><span class="hs-identifier">toList</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-56"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Applicative.html#"><span class="hs-identifier">Control.Applicative</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#Applicative"><span class="hs-identifier">Applicative</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#liftA2"><span class="hs-identifier">liftA2</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Control.Applicative</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Applicative</span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">liftA2</span><span class="hs-special">,</span><span> </span><span class="hs-special">(</span><span class="hs-operator">&lt;$&gt;</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-59"></span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Foldable</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Foldable</span><span class="hs-special">(</span><span class="hs-identifier">foldMap</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">toList</span><span class="hs-special">)</span><span>
</span><span id="line-60"></span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Monoid</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Monoid</span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-61"></span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Traversable</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Traversable</span><span class="hs-special">(</span><span class="hs-identifier">traverse</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-64"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.html#"><span class="hs-identifier">Control.Monad</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#liftM"><span class="hs-identifier">liftM</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-65"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.Fix.html#"><span class="hs-identifier">Control.Monad.Fix</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Control.Monad.Fix.html#MonadFix"><span class="hs-identifier">MonadFix</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Function.html#fix"><span class="hs-identifier">fix</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-66"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.Sequence.html"><span class="hs-identifier">Data.Sequence</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier">Seq</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#empty"><span class="hs-identifier">empty</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#singleton"><span class="hs-identifier">singleton</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3C%7C"><span class="hs-operator">(&lt;|)</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%7C%3E"><span class="hs-operator">(|&gt;)</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#fromList"><span class="hs-identifier">fromList</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-67"></span><span>            </span><span class="annot"><a href="Data.Sequence.Internal.html#ViewL"><span class="hs-identifier">ViewL</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#ViewR"><span class="hs-identifier">ViewR</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#viewl"><span class="hs-identifier">viewl</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#viewr"><span class="hs-identifier">viewr</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-68"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Typeable.html#"><span class="hs-identifier">Data.Typeable</span></a></span><span>
</span><span id="line-69"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#"><span class="hs-identifier">Control.DeepSeq</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier">NFData</span></a></span><span class="hs-special">(</span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#rnf"><span class="hs-identifier">rnf</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">

#ifdef __GLASGOW_HASKELL__
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Data.html#"><span class="hs-identifier">Data.Data</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Data.html#Data"><span class="hs-identifier">Data</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-73"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/GHC.Generics.html#"><span class="hs-identifier">GHC.Generics</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Generics.html#Generic"><span class="hs-identifier">Generic</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Generics.html#Generic1"><span class="hs-identifier">Generic1</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-76"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.Zip.html#"><span class="hs-identifier">Control.Monad.Zip</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Control.Monad.Zip.html#MonadZip"><span class="hs-identifier">MonadZip</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">

#if MIN_VERSION_base(4,8,0)
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Coerce.html#"><span class="hs-identifier">Data.Coerce</span></a></span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#if MIN_VERSION_base(4,9,0)
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Functor.Classes.html#"><span class="hs-identifier">Data.Functor.Classes</span></a></span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#if (!MIN_VERSION_base(4,11,0)) &amp;&amp; MIN_VERSION_base(4,9,0)
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Semigroup</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Semigroup</span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#if !MIN_VERSION_base(4,8,0)
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Functor</span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="hs-operator">&lt;$</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-93"></span><span class="hs-comment">-- | Non-empty, possibly infinite, multi-way trees; also known as /rose trees/.</span><span>
</span><span id="line-94"></span><span id="local-6989586621679172269"><span id="local-6989586621679172272"><span id="local-6989586621679172273"><span id="local-6989586621679172274"></span></span></span></span><span class="hs-keyword">data</span><span> </span><span id="Tree"><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-var">Tree</span></a></span></span><span> </span><span id="local-6989586621679172638"><span class="annot"><a href="#local-6989586621679172638"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="Node"><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span></span><span> </span><span class="hs-special">{</span><span>
</span><span id="line-95"></span><span>        </span><span id="rootLabel"><span class="annot"><span class="annottext">forall a. Tree a -&gt; a
</span><a href="Data.Tree.html#rootLabel"><span class="hs-identifier hs-var hs-var">rootLabel</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621679172638"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- ^ label value</span><span>
</span><span id="line-96"></span><span>        </span><span id="subForest"><span class="annot"><span class="annottext">forall a. Tree a -&gt; [Tree a]
</span><a href="Data.Tree.html#subForest"><span class="hs-identifier hs-var hs-var">subForest</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172638"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span>   </span><span class="hs-comment">-- ^ zero or more child trees</span><span>
</span><span id="line-97"></span><span>    </span><span class="hs-special">}</span><span class="hs-cpp">
#ifdef __GLASGOW_HASKELL__
</span><span>  </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span> </span><span id="local-6989586621679172257"><span id="local-6989586621679172263"><span class="annot"><span class="annottext">Tree a -&gt; Tree a -&gt; Bool
(Tree a -&gt; Tree a -&gt; Bool)
-&gt; (Tree a -&gt; Tree a -&gt; Bool) -&gt; Eq (Tree a)
forall a. Eq a =&gt; Tree a -&gt; Tree a -&gt; Bool
forall a. (a -&gt; a -&gt; Bool) -&gt; (a -&gt; a -&gt; Bool) -&gt; Eq a
/= :: Tree a -&gt; Tree a -&gt; Bool
$c/= :: forall a. Eq a =&gt; Tree a -&gt; Tree a -&gt; Bool
== :: Tree a -&gt; Tree a -&gt; Bool
$c== :: forall a. Eq a =&gt; Tree a -&gt; Tree a -&gt; Bool
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Eq</span></span></span></span><span>
</span><span id="line-100"></span><span>           </span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172235"><span id="local-6989586621679172249"><span id="local-6989586621679172252"><span id="local-6989586621679172254"><span class="annot"><span class="annottext">ReadPrec [Tree a]
ReadPrec (Tree a)
Int -&gt; ReadS (Tree a)
ReadS [Tree a]
(Int -&gt; ReadS (Tree a))
-&gt; ReadS [Tree a]
-&gt; ReadPrec (Tree a)
-&gt; ReadPrec [Tree a]
-&gt; Read (Tree a)
forall a. Read a =&gt; ReadPrec [Tree a]
forall a. Read a =&gt; ReadPrec (Tree a)
forall a. Read a =&gt; Int -&gt; ReadS (Tree a)
forall a. Read a =&gt; ReadS [Tree a]
forall a.
(Int -&gt; ReadS a)
-&gt; ReadS [a] -&gt; ReadPrec a -&gt; ReadPrec [a] -&gt; Read a
readListPrec :: ReadPrec [Tree a]
$creadListPrec :: forall a. Read a =&gt; ReadPrec [Tree a]
readPrec :: ReadPrec (Tree a)
$creadPrec :: forall a. Read a =&gt; ReadPrec (Tree a)
readList :: ReadS [Tree a]
$creadList :: forall a. Read a =&gt; ReadS [Tree a]
readsPrec :: Int -&gt; ReadS (Tree a)
$creadsPrec :: forall a. Read a =&gt; Int -&gt; ReadS (Tree a)
</span><a href="../../base/src/GHC.Read.html#Read"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Read</span></a></span></span></span></span></span><span>
</span><span id="line-101"></span><span>           </span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172221"><span id="local-6989586621679172223"><span id="local-6989586621679172231"><span class="annot"><span class="annottext">Int -&gt; Tree a -&gt; ShowS
[Tree a] -&gt; ShowS
Tree a -&gt; String
(Int -&gt; Tree a -&gt; ShowS)
-&gt; (Tree a -&gt; String) -&gt; ([Tree a] -&gt; ShowS) -&gt; Show (Tree a)
forall a. Show a =&gt; Int -&gt; Tree a -&gt; ShowS
forall a. Show a =&gt; [Tree a] -&gt; ShowS
forall a. Show a =&gt; Tree a -&gt; String
forall a.
(Int -&gt; a -&gt; ShowS) -&gt; (a -&gt; String) -&gt; ([a] -&gt; ShowS) -&gt; Show a
showList :: [Tree a] -&gt; ShowS
$cshowList :: forall a. Show a =&gt; [Tree a] -&gt; ShowS
show :: Tree a -&gt; String
$cshow :: forall a. Show a =&gt; Tree a -&gt; String
showsPrec :: Int -&gt; Tree a -&gt; ShowS
$cshowsPrec :: forall a. Show a =&gt; Int -&gt; Tree a -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Show</span></a></span></span></span></span><span>
</span><span id="line-102"></span><span>           </span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172178"><span id="local-6989586621679172180"><span id="local-6989586621679172182"><span id="local-6989586621679172184"><span id="local-6989586621679172186"><span id="local-6989586621679172188"><span id="local-6989586621679172190"><span id="local-6989586621679172192"><span id="local-6989586621679172194"><span id="local-6989586621679172200"><span id="local-6989586621679172202"><span id="local-6989586621679172204"><span id="local-6989586621679172209"><span id="local-6989586621679172215"><span class="annot"><span class="annottext">Typeable (Tree a)
Typeable (Tree a)
-&gt; (forall (c :: * -&gt; *).
    (forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
    -&gt; (forall g. g -&gt; c g) -&gt; Tree a -&gt; c (Tree a))
-&gt; (forall (c :: * -&gt; *).
    (forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
    -&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c (Tree a))
-&gt; (Tree a -&gt; Constr)
-&gt; (Tree a -&gt; DataType)
-&gt; (forall (t :: * -&gt; *) (c :: * -&gt; *).
    Typeable t =&gt;
    (forall d. Data d =&gt; c (t d)) -&gt; Maybe (c (Tree a)))
-&gt; (forall (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
    Typeable t =&gt;
    (forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c (Tree a)))
-&gt; ((forall b. Data b =&gt; b -&gt; b) -&gt; Tree a -&gt; Tree a)
-&gt; (forall r r'.
    (r -&gt; r' -&gt; r)
    -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r)
-&gt; (forall r r'.
    (r' -&gt; r -&gt; r)
    -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r)
-&gt; (forall u. (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; [u])
-&gt; (forall u. Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; u)
-&gt; (forall (m :: * -&gt; *).
    Monad m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a))
-&gt; (forall (m :: * -&gt; *).
    MonadPlus m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a))
-&gt; (forall (m :: * -&gt; *).
    MonadPlus m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a))
-&gt; Data (Tree a)
Tree a -&gt; DataType
Tree a -&gt; Constr
(forall b. Data b =&gt; b -&gt; b) -&gt; Tree a -&gt; Tree a
forall {a}. Data a =&gt; Typeable (Tree a)
forall a. Data a =&gt; Tree a -&gt; DataType
forall a. Data a =&gt; Tree a -&gt; Constr
forall a.
Data a =&gt;
(forall b. Data b =&gt; b -&gt; b) -&gt; Tree a -&gt; Tree a
forall a u.
Data a =&gt;
Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; u
forall a u. Data a =&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; [u]
forall a r r'.
Data a =&gt;
(r -&gt; r' -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
forall a r r'.
Data a =&gt;
(r' -&gt; r -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
forall a (m :: * -&gt; *).
(Data a, Monad m) =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
forall a (m :: * -&gt; *).
(Data a, MonadPlus m) =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
forall a (c :: * -&gt; *).
Data a =&gt;
(forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
-&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c (Tree a)
forall a (c :: * -&gt; *).
Data a =&gt;
(forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
-&gt; (forall g. g -&gt; c g) -&gt; Tree a -&gt; c (Tree a)
forall a (t :: * -&gt; *) (c :: * -&gt; *).
(Data a, Typeable t) =&gt;
(forall d. Data d =&gt; c (t d)) -&gt; Maybe (c (Tree a))
forall a (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
(Data a, Typeable t) =&gt;
(forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c (Tree a))
forall a.
Typeable a
-&gt; (forall (c :: * -&gt; *).
    (forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
    -&gt; (forall g. g -&gt; c g) -&gt; a -&gt; c a)
-&gt; (forall (c :: * -&gt; *).
    (forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
    -&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c a)
-&gt; (a -&gt; Constr)
-&gt; (a -&gt; DataType)
-&gt; (forall (t :: * -&gt; *) (c :: * -&gt; *).
    Typeable t =&gt;
    (forall d. Data d =&gt; c (t d)) -&gt; Maybe (c a))
-&gt; (forall (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
    Typeable t =&gt;
    (forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c a))
-&gt; ((forall b. Data b =&gt; b -&gt; b) -&gt; a -&gt; a)
-&gt; (forall r r'.
    (r -&gt; r' -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; a -&gt; r)
-&gt; (forall r r'.
    (r' -&gt; r -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; a -&gt; r)
-&gt; (forall u. (forall d. Data d =&gt; d -&gt; u) -&gt; a -&gt; [u])
-&gt; (forall u. Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; a -&gt; u)
-&gt; (forall (m :: * -&gt; *).
    Monad m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; a -&gt; m a)
-&gt; (forall (m :: * -&gt; *).
    MonadPlus m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; a -&gt; m a)
-&gt; (forall (m :: * -&gt; *).
    MonadPlus m =&gt;
    (forall d. Data d =&gt; d -&gt; m d) -&gt; a -&gt; m a)
-&gt; Data a
forall u. Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; u
forall u. (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; [u]
forall r r'.
(r -&gt; r' -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
forall r r'.
(r' -&gt; r -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
forall (m :: * -&gt; *).
Monad m =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
forall (m :: * -&gt; *).
MonadPlus m =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
forall (c :: * -&gt; *).
(forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
-&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c (Tree a)
forall (c :: * -&gt; *).
(forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
-&gt; (forall g. g -&gt; c g) -&gt; Tree a -&gt; c (Tree a)
forall (t :: * -&gt; *) (c :: * -&gt; *).
Typeable t =&gt;
(forall d. Data d =&gt; c (t d)) -&gt; Maybe (c (Tree a))
forall (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
Typeable t =&gt;
(forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c (Tree a))
gmapMo :: forall (m :: * -&gt; *).
MonadPlus m =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
$cgmapMo :: forall a (m :: * -&gt; *).
(Data a, MonadPlus m) =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
gmapMp :: forall (m :: * -&gt; *).
MonadPlus m =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
$cgmapMp :: forall a (m :: * -&gt; *).
(Data a, MonadPlus m) =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
gmapM :: forall (m :: * -&gt; *).
Monad m =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
$cgmapM :: forall a (m :: * -&gt; *).
(Data a, Monad m) =&gt;
(forall d. Data d =&gt; d -&gt; m d) -&gt; Tree a -&gt; m (Tree a)
gmapQi :: forall u. Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; u
$cgmapQi :: forall a u.
Data a =&gt;
Int -&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; u
gmapQ :: forall u. (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; [u]
$cgmapQ :: forall a u. Data a =&gt; (forall d. Data d =&gt; d -&gt; u) -&gt; Tree a -&gt; [u]
gmapQr :: forall r r'.
(r' -&gt; r -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
$cgmapQr :: forall a r r'.
Data a =&gt;
(r' -&gt; r -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
gmapQl :: forall r r'.
(r -&gt; r' -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
$cgmapQl :: forall a r r'.
Data a =&gt;
(r -&gt; r' -&gt; r) -&gt; r -&gt; (forall d. Data d =&gt; d -&gt; r') -&gt; Tree a -&gt; r
gmapT :: (forall b. Data b =&gt; b -&gt; b) -&gt; Tree a -&gt; Tree a
$cgmapT :: forall a.
Data a =&gt;
(forall b. Data b =&gt; b -&gt; b) -&gt; Tree a -&gt; Tree a
dataCast2 :: forall (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
Typeable t =&gt;
(forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c (Tree a))
$cdataCast2 :: forall a (t :: * -&gt; * -&gt; *) (c :: * -&gt; *).
(Data a, Typeable t) =&gt;
(forall d e. (Data d, Data e) =&gt; c (t d e)) -&gt; Maybe (c (Tree a))
dataCast1 :: forall (t :: * -&gt; *) (c :: * -&gt; *).
Typeable t =&gt;
(forall d. Data d =&gt; c (t d)) -&gt; Maybe (c (Tree a))
$cdataCast1 :: forall a (t :: * -&gt; *) (c :: * -&gt; *).
(Data a, Typeable t) =&gt;
(forall d. Data d =&gt; c (t d)) -&gt; Maybe (c (Tree a))
dataTypeOf :: Tree a -&gt; DataType
$cdataTypeOf :: forall a. Data a =&gt; Tree a -&gt; DataType
toConstr :: Tree a -&gt; Constr
$ctoConstr :: forall a. Data a =&gt; Tree a -&gt; Constr
gunfold :: forall (c :: * -&gt; *).
(forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
-&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c (Tree a)
$cgunfold :: forall a (c :: * -&gt; *).
Data a =&gt;
(forall b r. Data b =&gt; c (b -&gt; r) -&gt; c r)
-&gt; (forall r. r -&gt; c r) -&gt; Constr -&gt; c (Tree a)
gfoldl :: forall (c :: * -&gt; *).
(forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
-&gt; (forall g. g -&gt; c g) -&gt; Tree a -&gt; c (Tree a)
$cgfoldl :: forall a (c :: * -&gt; *).
Data a =&gt;
(forall d b. Data d =&gt; c (d -&gt; b) -&gt; d -&gt; c b)
-&gt; (forall g. g -&gt; c g) -&gt; Tree a -&gt; c (Tree a)
</span><a href="../../base/src/Data.Data.html#Data"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Data</span></a></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span>
</span><span id="line-103"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">(forall x. Tree a -&gt; Rep (Tree a) x)
-&gt; (forall x. Rep (Tree a) x -&gt; Tree a) -&gt; Generic (Tree a)
forall x. Rep (Tree a) x -&gt; Tree a
forall x. Tree a -&gt; Rep (Tree a) x
forall a.
(forall x. a -&gt; Rep a x) -&gt; (forall x. Rep a x -&gt; a) -&gt; Generic a
forall a x. Rep (Tree a) x -&gt; Tree a
forall a x. Tree a -&gt; Rep (Tree a) x
$cto :: forall a x. Rep (Tree a) x -&gt; Tree a
$cfrom :: forall a x. Tree a -&gt; Rep (Tree a) x
</span><a href="../../base/src/GHC.Generics.html#Generic"><span class="hs-identifier hs-var hs-var hs-var hs-var">Generic</span></a></span><span>  </span><span class="hs-comment">-- ^ @since 0.5.8</span><span>
</span><span id="line-104"></span><span>           </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">(forall a. Tree a -&gt; Rep1 Tree a)
-&gt; (forall a. Rep1 Tree a -&gt; Tree a) -&gt; Generic1 Tree
forall a. Rep1 Tree a -&gt; Tree a
forall a. Tree a -&gt; Rep1 Tree a
forall k (f :: k -&gt; *).
(forall (a :: k). f a -&gt; Rep1 f a)
-&gt; (forall (a :: k). Rep1 f a -&gt; f a) -&gt; Generic1 f
$cto1 :: forall a. Rep1 Tree a -&gt; Tree a
$cfrom1 :: forall a. Tree a -&gt; Rep1 Tree a
</span><a href="../../base/src/GHC.Generics.html#Generic1"><span class="hs-identifier hs-var hs-var hs-var hs-var">Generic1</span></a></span><span> </span><span class="hs-comment">-- ^ @since 0.5.8</span><span>
</span><span id="line-105"></span><span>           </span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span>  </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Eq</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">Read</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">Show</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-110"></span><span class="hs-comment">-- | This type synonym exists primarily for historical</span><span>
</span><span id="line-111"></span><span class="hs-comment">-- reasons.</span><span>
</span><span id="line-112"></span><span class="hs-keyword">type</span><span> </span><span id="Forest"><span class="annot"><a href="Data.Tree.html#Forest"><span class="hs-identifier hs-var">Forest</span></a></span></span><span> </span><span id="local-6989586621679172168"><span class="annot"><a href="#local-6989586621679172168"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172168"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-cpp">

#if MIN_VERSION_base(4,9,0)
</span><span class="hs-comment">-- | @since 0.5.9</span><span>
</span><span id="line-116"></span><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../base/src/Data.Functor.Classes.html#Eq1"><span class="hs-identifier hs-type">Eq1</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-117"></span><span>  </span><span id="local-6989586621679172164"><span class="annot"><span class="annottext">liftEq :: forall a b. (a -&gt; b -&gt; Bool) -&gt; Tree a -&gt; Tree b -&gt; Bool
</span><a href="../../base/src/Data.Functor.Classes.html#liftEq"><span class="hs-identifier hs-var hs-var hs-var hs-var">liftEq</span></a></span></span><span> </span><span id="local-6989586621679172162"><span class="annot"><span class="annottext">a -&gt; b -&gt; Bool
</span><a href="#local-6989586621679172162"><span class="hs-identifier hs-var">eq</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Bool
</span><a href="#local-6989586621679172161"><span class="hs-identifier hs-var">leq</span></a></span><span>
</span><span id="line-118"></span><span>    </span><span class="hs-keyword">where</span><span>
</span><span id="line-119"></span><span>      </span><span id="local-6989586621679172161"><span class="annot"><span class="annottext">leq :: Tree a -&gt; Tree b -&gt; Bool
</span><a href="#local-6989586621679172161"><span class="hs-identifier hs-var hs-var">leq</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172158"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172158"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679172157"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172157"><span class="hs-identifier hs-var">fr</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172156"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172156"><span class="hs-identifier hs-var">a'</span></a></span></span><span> </span><span id="local-6989586621679172155"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172155"><span class="hs-identifier hs-var">fr'</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; Bool
</span><a href="#local-6989586621679172162"><span class="hs-identifier hs-var">eq</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172158"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172156"><span class="hs-identifier hs-var">a'</span></a></span><span> </span><span class="annot"><span class="annottext">Bool -&gt; Bool -&gt; Bool
</span><span class="hs-operator hs-var">&amp;&amp;</span></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b -&gt; Bool) -&gt; [Tree a] -&gt; [Tree b] -&gt; Bool
forall (f :: * -&gt; *) a b.
Eq1 f =&gt;
(a -&gt; b -&gt; Bool) -&gt; f a -&gt; f b -&gt; Bool
</span><a href="../../base/src/Data.Functor.Classes.html#liftEq"><span class="hs-identifier hs-var">liftEq</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Bool
</span><a href="#local-6989586621679172161"><span class="hs-identifier hs-var">leq</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172157"><span class="hs-identifier hs-var">fr</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172155"><span class="hs-identifier hs-var">fr'</span></a></span><span>
</span><span id="line-120"></span><span>
</span><span id="line-121"></span><span class="hs-comment">-- | @since 0.5.9</span><span>
</span><span id="line-122"></span><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../base/src/Data.Functor.Classes.html#Ord1"><span class="hs-identifier hs-type">Ord1</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-123"></span><span>  </span><span id="local-6989586621679172148"><span class="annot"><span class="annottext">liftCompare :: forall a b. (a -&gt; b -&gt; Ordering) -&gt; Tree a -&gt; Tree b -&gt; Ordering
</span><a href="../../base/src/Data.Functor.Classes.html#liftCompare"><span class="hs-identifier hs-var hs-var hs-var hs-var">liftCompare</span></a></span></span><span> </span><span id="local-6989586621679172146"><span class="annot"><span class="annottext">a -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679172146"><span class="hs-identifier hs-var">cmp</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Ordering
</span><a href="#local-6989586621679172145"><span class="hs-identifier hs-var">lcomp</span></a></span><span>
</span><span id="line-124"></span><span>    </span><span class="hs-keyword">where</span><span>
</span><span id="line-125"></span><span>      </span><span id="local-6989586621679172145"><span class="annot"><span class="annottext">lcomp :: Tree a -&gt; Tree b -&gt; Ordering
</span><a href="#local-6989586621679172145"><span class="hs-identifier hs-var hs-var">lcomp</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172140"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172140"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679172139"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172139"><span class="hs-identifier hs-var">fr</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172138"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172138"><span class="hs-identifier hs-var">a'</span></a></span></span><span> </span><span id="local-6989586621679172137"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172137"><span class="hs-identifier hs-var">fr'</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; Ordering
</span><a href="#local-6989586621679172146"><span class="hs-identifier hs-var">cmp</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172140"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172138"><span class="hs-identifier hs-var">a'</span></a></span><span> </span><span class="annot"><span class="annottext">Ordering -&gt; Ordering -&gt; Ordering
forall a. Semigroup a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Base.html#%3C%3E"><span class="hs-operator hs-var">&lt;&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b -&gt; Ordering) -&gt; [Tree a] -&gt; [Tree b] -&gt; Ordering
forall (f :: * -&gt; *) a b.
Ord1 f =&gt;
(a -&gt; b -&gt; Ordering) -&gt; f a -&gt; f b -&gt; Ordering
</span><a href="../../base/src/Data.Functor.Classes.html#liftCompare"><span class="hs-identifier hs-var">liftCompare</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Ordering
</span><a href="#local-6989586621679172145"><span class="hs-identifier hs-var">lcomp</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172139"><span class="hs-identifier hs-var">fr</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172137"><span class="hs-identifier hs-var">fr'</span></a></span><span>
</span><span id="line-126"></span><span>
</span><span id="line-127"></span><span class="hs-comment">-- | @since 0.5.9</span><span>
</span><span id="line-128"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679172134"><span class="annot"><a href="../../base/src/Data.Functor.Classes.html#Show1"><span class="hs-identifier hs-type">Show1</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-129"></span><span>  </span><span id="local-6989586621679172128"><span class="annot"><span class="annottext">liftShowsPrec :: forall a.
(Int -&gt; a -&gt; ShowS) -&gt; ([a] -&gt; ShowS) -&gt; Int -&gt; Tree a -&gt; ShowS
</span><a href="../../base/src/Data.Functor.Classes.html#liftShowsPrec"><span class="hs-identifier hs-var hs-var hs-var hs-var">liftShowsPrec</span></a></span></span><span> </span><span id="local-6989586621679172126"><span class="annot"><span class="annottext">Int -&gt; a -&gt; ShowS
</span><a href="#local-6989586621679172126"><span class="hs-identifier hs-var">shw</span></a></span></span><span> </span><span id="local-6989586621679172125"><span class="annot"><span class="annottext">[a] -&gt; ShowS
</span><a href="#local-6989586621679172125"><span class="hs-identifier hs-var">shwl</span></a></span></span><span> </span><span id="local-6989586621679172124"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679172124"><span class="hs-identifier hs-var">p</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172123"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172123"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679172122"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172122"><span class="hs-identifier hs-var">fr</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; ShowS -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#showParen"><span class="hs-identifier hs-var">showParen</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679172124"><span class="hs-identifier hs-var">p</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">10</span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">(ShowS -&gt; ShowS) -&gt; ShowS -&gt; ShowS
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span>
</span><span id="line-130"></span><span>        </span><span class="annot"><span class="annottext">String -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#showString"><span class="hs-identifier hs-var">showString</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Node {rootLabel = &quot;</span></span><span> </span><span class="annot"><span class="annottext">ShowS -&gt; ShowS -&gt; ShowS
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; ShowS
</span><a href="#local-6989586621679172126"><span class="hs-identifier hs-var">shw</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172123"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">ShowS -&gt; ShowS -&gt; ShowS
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">String -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#showString"><span class="hs-identifier hs-var">showString</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;, &quot;</span></span><span> </span><span class="annot"><span class="annottext">ShowS -&gt; ShowS -&gt; ShowS
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span>
</span><span id="line-131"></span><span>          </span><span class="annot"><span class="annottext">String -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#showString"><span class="hs-identifier hs-var">showString</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;subForest = &quot;</span></span><span> </span><span class="annot"><span class="annottext">ShowS -&gt; ShowS -&gt; ShowS
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(Int -&gt; a -&gt; ShowS) -&gt; ([a] -&gt; ShowS) -&gt; [Tree a] -&gt; ShowS
forall (f :: * -&gt; *) a.
Show1 f =&gt;
(Int -&gt; a -&gt; ShowS) -&gt; ([a] -&gt; ShowS) -&gt; [f a] -&gt; ShowS
</span><a href="../../base/src/Data.Functor.Classes.html#liftShowList"><span class="hs-identifier hs-var">liftShowList</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; a -&gt; ShowS
</span><a href="#local-6989586621679172126"><span class="hs-identifier hs-var">shw</span></a></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; ShowS
</span><a href="#local-6989586621679172125"><span class="hs-identifier hs-var">shwl</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172122"><span class="hs-identifier hs-var">fr</span></a></span><span> </span><span class="annot"><span class="annottext">ShowS -&gt; ShowS -&gt; ShowS
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span>
</span><span id="line-132"></span><span>          </span><span class="annot"><span class="annottext">String -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#showString"><span class="hs-identifier hs-var">showString</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;}&quot;</span></span><span>
</span><span id="line-133"></span><span>
</span><span id="line-134"></span><span class="hs-comment">-- | @since 0.5.9</span><span>
</span><span id="line-135"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679172110"><span id="local-6989586621679172112"><span id="local-6989586621679172114"><span class="annot"><a href="../../base/src/Data.Functor.Classes.html#Read1"><span class="hs-identifier hs-type">Read1</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-136"></span><span>  </span><span id="local-6989586621679172083"><span class="annot"><span class="annottext">liftReadsPrec :: forall a. (Int -&gt; ReadS a) -&gt; ReadS [a] -&gt; Int -&gt; ReadS (Tree a)
</span><a href="../../base/src/Data.Functor.Classes.html#liftReadsPrec"><span class="hs-identifier hs-var hs-var hs-var hs-var">liftReadsPrec</span></a></span></span><span> </span><span id="local-6989586621679172081"><span class="annot"><span class="annottext">Int -&gt; ReadS a
</span><a href="#local-6989586621679172081"><span class="hs-identifier hs-var">rd</span></a></span></span><span> </span><span id="local-6989586621679172080"><span class="annot"><span class="annottext">ReadS [a]
</span><a href="#local-6989586621679172080"><span class="hs-identifier hs-var">rdl</span></a></span></span><span> </span><span id="local-6989586621679172079"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679172079"><span class="hs-identifier hs-var">p</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool -&gt; ReadS (Tree a) -&gt; ReadS (Tree a)
forall a. Bool -&gt; ReadS a -&gt; ReadS a
</span><a href="../../base/src/GHC.Read.html#readParen"><span class="hs-identifier hs-var">readParen</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679172079"><span class="hs-identifier hs-var">p</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Bool
forall a. Ord a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">&gt;</span></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">10</span></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">(ReadS (Tree a) -&gt; ReadS (Tree a))
-&gt; ReadS (Tree a) -&gt; ReadS (Tree a)
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span>
</span><span id="line-137"></span><span>    </span><span class="hs-glyph">\</span><span id="local-6989586621679172077"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172077"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-138"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Node&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172076"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172076"><span class="hs-identifier hs-var">s1</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172077"><span class="hs-identifier hs-var">s</span></a></span><span>
</span><span id="line-139"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;{&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172074"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172074"><span class="hs-identifier hs-var">s2</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172076"><span class="hs-identifier hs-var">s1</span></a></span><span>
</span><span id="line-140"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;rootLabel&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172073"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172073"><span class="hs-identifier hs-var">s3</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172074"><span class="hs-identifier hs-var">s2</span></a></span><span>
</span><span id="line-141"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;=&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172072"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172072"><span class="hs-identifier hs-var">s4</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172073"><span class="hs-identifier hs-var">s3</span></a></span><span>
</span><span id="line-142"></span><span>      </span><span class="hs-special">(</span><span id="local-6989586621679172071"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172071"><span class="hs-identifier hs-var">a</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172070"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172070"><span class="hs-identifier hs-var">s5</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Int -&gt; ReadS a
</span><a href="#local-6989586621679172081"><span class="hs-identifier hs-var">rd</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172072"><span class="hs-identifier hs-var">s4</span></a></span><span>
</span><span id="line-143"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;,&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172069"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172069"><span class="hs-identifier hs-var">s6</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172070"><span class="hs-identifier hs-var">s5</span></a></span><span>
</span><span id="line-144"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;subForest&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172068"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172068"><span class="hs-identifier hs-var">s7</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172069"><span class="hs-identifier hs-var">s6</span></a></span><span>
</span><span id="line-145"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;=&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172067"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172067"><span class="hs-identifier hs-var">s8</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172068"><span class="hs-identifier hs-var">s7</span></a></span><span>
</span><span id="line-146"></span><span>      </span><span class="hs-special">(</span><span id="local-6989586621679172066"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172066"><span class="hs-identifier hs-var">fr</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172065"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172065"><span class="hs-identifier hs-var">s9</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(Int -&gt; ReadS a) -&gt; ReadS [a] -&gt; ReadS [Tree a]
forall (f :: * -&gt; *) a.
Read1 f =&gt;
(Int -&gt; ReadS a) -&gt; ReadS [a] -&gt; ReadS [f a]
</span><a href="../../base/src/Data.Functor.Classes.html#liftReadList"><span class="hs-identifier hs-var">liftReadList</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; ReadS a
</span><a href="#local-6989586621679172081"><span class="hs-identifier hs-var">rd</span></a></span><span> </span><span class="annot"><span class="annottext">ReadS [a]
</span><a href="#local-6989586621679172080"><span class="hs-identifier hs-var">rdl</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172067"><span class="hs-identifier hs-var">s8</span></a></span><span>
</span><span id="line-147"></span><span>      </span><span class="hs-special">(</span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;}&quot;</span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679172063"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172063"><span class="hs-identifier hs-var">s10</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">ReadS String
</span><a href="../../base/src/GHC.Read.html#lex"><span class="hs-identifier hs-var">lex</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172065"><span class="hs-identifier hs-var">s9</span></a></span><span>
</span><span id="line-148"></span><span>      </span><span class="annot"><span class="annottext">(Tree a, String) -&gt; [(Tree a, String)]
forall (f :: * -&gt; *) a. Applicative f =&gt; a -&gt; f a
</span><a href="../../base/src/GHC.Base.html#pure"><span class="hs-identifier hs-var">pure</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172071"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172066"><span class="hs-identifier hs-var">fr</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679172063"><span class="hs-identifier hs-var">s10</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-151"></span><span class="hs-identifier">INSTANCE_TYPEABLE1</span><span class="hs-special">(</span><span class="hs-identifier">Tree</span><span class="hs-special">)</span><span>
</span><span id="line-152"></span><span>
</span><span id="line-153"></span><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Functor"><span class="hs-identifier hs-type">Functor</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-154"></span><span>    </span><span id="local-6989586621679172058"><span class="annot"><span class="annottext">fmap :: forall a b. (a -&gt; b) -&gt; Tree a -&gt; Tree b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-identifier hs-var hs-var hs-var hs-var">fmap</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; b) -&gt; Tree a -&gt; Tree b
forall a b. (a -&gt; b) -&gt; Tree a -&gt; Tree b
</span><a href="Data.Tree.html#fmapTree"><span class="hs-identifier hs-var">fmapTree</span></a></span><span>
</span><span id="line-155"></span><span>    </span><span id="local-6989586621679172055"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172055"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679172054"><span class="annot"><span class="annottext">&lt;$ :: forall a b. a -&gt; Tree b -&gt; Tree a
</span><a href="../../base/src/GHC.Base.html#%3C%24"><span class="hs-operator hs-var hs-var hs-var hs-var">&lt;$</span></a></span></span><span> </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679172052"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172052"><span class="hs-identifier hs-var">ts</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172055"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree b -&gt; Tree a) -&gt; [Tree b] -&gt; [Tree a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172055"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree b -&gt; Tree a
forall (f :: * -&gt; *) a b. Functor f =&gt; a -&gt; f b -&gt; f a
</span><a href="../../base/src/GHC.Base.html#%3C%24"><span class="hs-operator hs-var">&lt;$</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172052"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-156"></span><span>
</span><span id="line-157"></span><span id="local-6989586621679172050"><span id="local-6989586621679172051"><span class="annot"><a href="Data.Tree.html#fmapTree"><span class="hs-identifier hs-type">fmapTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172051"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172050"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172051"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172050"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-158"></span><span id="fmapTree"><span class="annot"><span class="annottext">fmapTree :: forall a b. (a -&gt; b) -&gt; Tree a -&gt; Tree b
</span><a href="Data.Tree.html#fmapTree"><span class="hs-identifier hs-var hs-var">fmapTree</span></a></span></span><span> </span><span id="local-6989586621679172049"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172049"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172048"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172048"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679172047"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172047"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172049"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172048"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b) -&gt; [Tree a] -&gt; [Tree b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; b) -&gt; Tree a -&gt; Tree b
forall a b. (a -&gt; b) -&gt; Tree a -&gt; Tree b
</span><a href="Data.Tree.html#fmapTree"><span class="hs-identifier hs-var">fmapTree</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172049"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172047"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#if MIN_VERSION_base(4,8,0)
</span><span class="hs-comment">-- Safe coercions were introduced in 4.7.0, but I am not sure if they played</span><span>
</span><span id="line-161"></span><span class="hs-comment">-- well enough with RULES to do what we want.</span><span>
</span><span id="line-162"></span><span class="hs-pragma">{-# NOINLINE</span><span> </span><span class="hs-pragma">[</span><span class="hs-pragma">1</span><span class="hs-pragma">]</span><span> </span><span class="annot"><a href="Data.Tree.html#fmapTree"><span class="hs-pragma hs-type">fmapTree</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-163"></span><span class="hs-pragma">{-# RULES</span><span>
</span><span id="line-164"></span><span class="annot"><span class="hs-pragma">&quot;fmapTree/coerce&quot;</span></span><span> </span><span class="annot"><a href="Data.Tree.html#fmapTree"><span class="hs-pragma hs-type">fmapTree</span></a></span><span> </span><span class="annot"><span class="hs-pragma hs-type">coerce</span></span><span> </span><span class="hs-pragma">=</span><span> </span><span class="annot"><span class="hs-pragma hs-type">coerce</span></span><span>
</span><span id="line-165"></span><span> </span><span class="hs-pragma">#-}</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-168"></span><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Applicative"><span class="hs-identifier hs-type">Applicative</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-169"></span><span>    </span><span id="local-6989586621679172037"><span class="annot"><span class="annottext">pure :: forall a. a -&gt; Tree a
</span><a href="../../base/src/GHC.Base.html#pure"><span class="hs-identifier hs-var hs-var hs-var hs-var">pure</span></a></span></span><span> </span><span id="local-6989586621679172036"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172036"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172036"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-170"></span><span>    </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172033"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172033"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679172032"><span class="annot"><span class="annottext">[Tree (a -&gt; b)]
</span><a href="#local-6989586621679172032"><span class="hs-identifier hs-var">tfs</span></a></span></span><span> </span><span id="local-6989586621679172031"><span class="annot"><span class="annottext">&lt;*&gt; :: forall a b. Tree (a -&gt; b) -&gt; Tree a -&gt; Tree b
</span><a href="../../base/src/GHC.Base.html#%3C%2A%3E"><span class="hs-operator hs-var hs-var hs-var hs-var">&lt;*&gt;</span></a></span></span><span> </span><span id="local-6989586621679172030"><span class="annot"><span class="annottext">tx :: Tree a
</span><a href="#local-6989586621679172030"><span class="hs-identifier hs-var">tx</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172029"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172029"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679172028"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172028"><span class="hs-identifier hs-var">txs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-171"></span><span>        </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172033"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172029"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b) -&gt; [Tree a] -&gt; [Tree b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679172033"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">(a -&gt; b) -&gt; Tree a -&gt; Tree b
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/Data.Functor.html#%3C%24%3E"><span class="hs-operator hs-var">&lt;$&gt;</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172028"><span class="hs-identifier hs-var">txs</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b] -&gt; [Tree b] -&gt; [Tree b]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree (a -&gt; b) -&gt; Tree b) -&gt; [Tree (a -&gt; b)] -&gt; [Tree b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree (a -&gt; b) -&gt; Tree a -&gt; Tree b
forall (f :: * -&gt; *) a b. Applicative f =&gt; f (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/GHC.Base.html#%3C%2A%3E"><span class="hs-operator hs-var">&lt;*&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679172030"><span class="hs-identifier hs-var">tx</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree (a -&gt; b)]
</span><a href="#local-6989586621679172032"><span class="hs-identifier hs-var">tfs</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#if MIN_VERSION_base(4,10,0)
</span><span>    </span><span id="local-6989586621679172024"><span class="annot"><span class="annottext">liftA2 :: forall a b c. (a -&gt; b -&gt; c) -&gt; Tree a -&gt; Tree b -&gt; Tree c
</span><a href="#local-6989586621679172024"><span class="hs-identifier hs-var hs-var hs-var hs-var">liftA2</span></a></span></span><span> </span><span id="local-6989586621679172023"><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679172023"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172022"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172022"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679172021"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172021"><span class="hs-identifier hs-var">txs</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679172020"><span class="annot"><span class="annottext">ty :: Tree b
</span><a href="#local-6989586621679172020"><span class="hs-identifier hs-var">ty</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172019"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172019"><span class="hs-identifier hs-var">y</span></a></span></span><span> </span><span id="local-6989586621679172018"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172018"><span class="hs-identifier hs-var">tys</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-174"></span><span>        </span><span class="annot"><span class="annottext">c -&gt; [Tree c] -&gt; Tree c
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679172023"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172022"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172019"><span class="hs-identifier hs-var">y</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree b -&gt; Tree c) -&gt; [Tree b] -&gt; [Tree c]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679172023"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172022"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">(b -&gt; c) -&gt; Tree b -&gt; Tree c
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/Data.Functor.html#%3C%24%3E"><span class="hs-operator hs-var">&lt;$&gt;</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172018"><span class="hs-identifier hs-var">tys</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree c] -&gt; [Tree c] -&gt; [Tree c]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree c) -&gt; [Tree a] -&gt; [Tree c]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621679172017"><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679172017"><span class="hs-identifier hs-var">tx</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">(a -&gt; b -&gt; c) -&gt; Tree a -&gt; Tree b -&gt; Tree c
forall (f :: * -&gt; *) a b c.
Applicative f =&gt;
(a -&gt; b -&gt; c) -&gt; f a -&gt; f b -&gt; f c
</span><a href="../../base/src/GHC.Base.html#liftA2"><span class="hs-identifier hs-var">liftA2</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679172023"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679172017"><span class="hs-identifier hs-var">tx</span></a></span><span> </span><span class="annot"><span class="annottext">Tree b
</span><a href="#local-6989586621679172020"><span class="hs-identifier hs-var">ty</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172021"><span class="hs-identifier hs-var">txs</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>    </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172014"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172014"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679172013"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172013"><span class="hs-identifier hs-var">txs</span></a></span></span><span> </span><span id="local-6989586621679172012"><span class="annot"><span class="annottext">&lt;* :: forall a b. Tree a -&gt; Tree b -&gt; Tree a
</span><a href="../../base/src/GHC.Base.html#%3C%2A"><span class="hs-operator hs-var hs-var hs-var hs-var">&lt;*</span></a></span></span><span> </span><span id="local-6989586621679172010"><span class="annot"><span class="annottext">ty :: Tree b
</span><a href="#local-6989586621679172010"><span class="hs-identifier hs-var">ty</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679172009"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172009"><span class="hs-identifier hs-var">tys</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-177"></span><span>        </span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172014"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree b -&gt; Tree a) -&gt; [Tree b] -&gt; [Tree a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679172014"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree b -&gt; Tree a
forall (f :: * -&gt; *) a b. Functor f =&gt; a -&gt; f b -&gt; f a
</span><a href="../../base/src/GHC.Base.html#%3C%24"><span class="hs-operator hs-var">&lt;$</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172009"><span class="hs-identifier hs-var">tys</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a] -&gt; [Tree a] -&gt; [Tree a]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree a) -&gt; [Tree a] -&gt; [Tree a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Tree a
forall (f :: * -&gt; *) a b. Applicative f =&gt; f a -&gt; f b -&gt; f a
</span><a href="../../base/src/GHC.Base.html#%3C%2A"><span class="hs-operator hs-var">&lt;*</span></a></span><span> </span><span class="annot"><span class="annottext">Tree b
</span><a href="#local-6989586621679172010"><span class="hs-identifier hs-var">ty</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172013"><span class="hs-identifier hs-var">txs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-178"></span><span>    </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679172007"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172007"><span class="hs-identifier hs-var">txs</span></a></span></span><span> </span><span id="local-6989586621679172006"><span class="annot"><span class="annottext">*&gt; :: forall a b. Tree a -&gt; Tree b -&gt; Tree b
</span><a href="../../base/src/GHC.Base.html#%2A%3E"><span class="hs-operator hs-var hs-var hs-var hs-var">*&gt;</span></a></span></span><span> </span><span id="local-6989586621679172005"><span class="annot"><span class="annottext">ty :: Tree b
</span><a href="#local-6989586621679172005"><span class="hs-identifier hs-var">ty</span></a></span></span><span class="hs-glyph">@</span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679172004"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172004"><span class="hs-identifier hs-var">y</span></a></span></span><span> </span><span id="local-6989586621679172003"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172003"><span class="hs-identifier hs-var">tys</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-179"></span><span>        </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679172004"><span class="hs-identifier hs-var">y</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679172003"><span class="hs-identifier hs-var">tys</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b] -&gt; [Tree b] -&gt; [Tree b]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b) -&gt; [Tree a] -&gt; [Tree b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree a -&gt; Tree b -&gt; Tree b
forall (f :: * -&gt; *) a b. Applicative f =&gt; f a -&gt; f b -&gt; f b
</span><a href="../../base/src/GHC.Base.html#%2A%3E"><span class="hs-operator hs-var">*&gt;</span></a></span><span> </span><span class="annot"><span class="annottext">Tree b
</span><a href="#local-6989586621679172005"><span class="hs-identifier hs-var">ty</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679172007"><span class="hs-identifier hs-var">txs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-180"></span><span>
</span><span id="line-181"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679171998"><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-182"></span><span>    </span><span id="local-6989586621679171994"><span class="annot"><span class="annottext">return :: forall a. a -&gt; Tree a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var hs-var hs-var hs-var">return</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree a
forall (f :: * -&gt; *) a. Applicative f =&gt; a -&gt; f a
</span><a href="../../base/src/GHC.Base.html#pure"><span class="hs-identifier hs-var">pure</span></a></span><span>
</span><span id="line-183"></span><span>    </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171992"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171992"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171991"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171991"><span class="hs-identifier hs-var">ts</span></a></span></span><span> </span><span id="local-6989586621679171990"><span class="annot"><span class="annottext">&gt;&gt;= :: forall a b. Tree a -&gt; (a -&gt; Tree b) -&gt; Tree b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var hs-var hs-var hs-var">&gt;&gt;=</span></a></span></span><span> </span><span id="local-6989586621679171989"><span class="annot"><span class="annottext">a -&gt; Tree b
</span><a href="#local-6989586621679171989"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree b
</span><a href="#local-6989586621679171989"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171992"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-184"></span><span>        </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171988"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171988"><span class="hs-identifier hs-var">x'</span></a></span></span><span> </span><span id="local-6989586621679171987"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171987"><span class="hs-identifier hs-var">ts'</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171988"><span class="hs-identifier hs-var">x'</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171987"><span class="hs-identifier hs-var">ts'</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b] -&gt; [Tree b] -&gt; [Tree b]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b) -&gt; [Tree a] -&gt; [Tree b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree a -&gt; (a -&gt; Tree b) -&gt; Tree b
forall (m :: * -&gt; *) a b. Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b
</span><a href="../../base/src/GHC.Base.html#%3E%3E%3D"><span class="hs-operator hs-var">&gt;&gt;=</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree b
</span><a href="#local-6989586621679171989"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171991"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-185"></span><span>
</span><span id="line-186"></span><span class="hs-comment">-- | @since 0.5.11</span><span>
</span><span id="line-187"></span><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.Fix.html#MonadFix"><span class="hs-identifier hs-type">MonadFix</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-188"></span><span>  </span><span id="local-6989586621679171981"><span class="annot"><span class="annottext">mfix :: forall a. (a -&gt; Tree a) -&gt; Tree a
</span><a href="../../base/src/Control.Monad.Fix.html#mfix"><span class="hs-identifier hs-var hs-var hs-var hs-var">mfix</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Tree a) -&gt; Tree a
forall a. (a -&gt; Tree a) -&gt; Tree a
</span><a href="Data.Tree.html#mfixTree"><span class="hs-identifier hs-var">mfixTree</span></a></span><span>
</span><span id="line-189"></span><span>
</span><span id="line-190"></span><span id="local-6989586621679171979"><span class="annot"><a href="Data.Tree.html#mfixTree"><span class="hs-identifier hs-type">mfixTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171979"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171979"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171979"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-191"></span><span id="mfixTree"><span class="annot"><span class="annottext">mfixTree :: forall a. (a -&gt; Tree a) -&gt; Tree a
</span><a href="Data.Tree.html#mfixTree"><span class="hs-identifier hs-var hs-var">mfixTree</span></a></span></span><span> </span><span id="local-6989586621679171975"><span class="annot"><span class="annottext">a -&gt; Tree a
</span><a href="#local-6989586621679171975"><span class="hs-identifier hs-var">f</span></a></span></span><span>
</span><span id="line-192"></span><span>  </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171974"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171974"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679171973"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171973"><span class="hs-identifier hs-var">children</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; Tree a) -&gt; Tree a
forall a. (a -&gt; a) -&gt; a
</span><a href="../../base/src/Data.Function.html#fix"><span class="hs-identifier hs-var">fix</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; Tree a
</span><a href="#local-6989586621679171975"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">(a -&gt; Tree a) -&gt; (Tree a -&gt; a) -&gt; Tree a -&gt; Tree a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; a
forall a. Tree a -&gt; a
</span><a href="Data.Tree.html#rootLabel"><span class="hs-identifier hs-var hs-var">rootLabel</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-193"></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171974"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Int -&gt; Tree a -&gt; Tree a) -&gt; [Int] -&gt; [Tree a] -&gt; [Tree a]
forall a b c. (a -&gt; b -&gt; c) -&gt; [a] -&gt; [b] -&gt; [c]
</span><a href="../../base/src/GHC.List.html#zipWith"><span class="hs-identifier hs-var">zipWith</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621679171971"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171971"><span class="hs-identifier hs-var">i</span></a></span></span><span> </span><span class="annot"><span class="annottext">Tree a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">(a -&gt; Tree a) -&gt; Tree a
forall a. (a -&gt; Tree a) -&gt; Tree a
</span><a href="Data.Tree.html#mfixTree"><span class="hs-identifier hs-var">mfixTree</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="annot"><span class="annottext">[Tree a] -&gt; Int -&gt; Tree a
forall a. [a] -&gt; Int -&gt; a
</span><a href="../../base/src/GHC.List.html#%21%21"><span class="hs-operator hs-var">!!</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679171971"><span class="hs-identifier hs-var">i</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([Tree a] -&gt; Tree a) -&gt; (a -&gt; [Tree a]) -&gt; a -&gt; Tree a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [Tree a]
forall a. Tree a -&gt; [Tree a]
</span><a href="Data.Tree.html#subForest"><span class="hs-identifier hs-var hs-var">subForest</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; [Tree a]) -&gt; (a -&gt; Tree a) -&gt; a -&gt; [Tree a]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Tree a
</span><a href="#local-6989586621679171975"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-194"></span><span>                    </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">0</span></span><span class="hs-glyph">..</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171973"><span class="hs-identifier hs-var">children</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-195"></span><span>
</span><span id="line-196"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679171959"><span id="local-6989586621679171961"><span id="local-6989586621679171963"><span class="annot"><a href="../../base/src/Data.Traversable.html#Traversable"><span class="hs-identifier hs-type">Traversable</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-197"></span><span>    </span><span id="local-6989586621679171950"><span class="annot"><span class="annottext">traverse :: forall (f :: * -&gt; *) a b.
Applicative f =&gt;
(a -&gt; f b) -&gt; Tree a -&gt; f (Tree b)
</span><a href="../../base/src/Data.Traversable.html#traverse"><span class="hs-identifier hs-var hs-var hs-var hs-var">traverse</span></a></span></span><span> </span><span id="local-6989586621679171948"><span class="annot"><span class="annottext">a -&gt; f b
</span><a href="#local-6989586621679171948"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171947"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171947"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171946"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171946"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; [Tree b] -&gt; Tree b) -&gt; f b -&gt; f [Tree b] -&gt; f (Tree b)
forall (f :: * -&gt; *) a b c.
Applicative f =&gt;
(a -&gt; b -&gt; c) -&gt; f a -&gt; f b -&gt; f c
</span><a href="../../base/src/GHC.Base.html#liftA2"><span class="hs-identifier hs-var">liftA2</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; f b
</span><a href="#local-6989586621679171948"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171947"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; f (Tree b)) -&gt; [Tree a] -&gt; f [Tree b]
forall (t :: * -&gt; *) (f :: * -&gt; *) a b.
(Traversable t, Applicative f) =&gt;
(a -&gt; f b) -&gt; t a -&gt; f (t b)
</span><a href="../../base/src/Data.Traversable.html#traverse"><span class="hs-identifier hs-var">traverse</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; f b) -&gt; Tree a -&gt; f (Tree b)
forall (t :: * -&gt; *) (f :: * -&gt; *) a b.
(Traversable t, Applicative f) =&gt;
(a -&gt; f b) -&gt; t a -&gt; f (t b)
</span><a href="../../base/src/Data.Traversable.html#traverse"><span class="hs-identifier hs-var">traverse</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; f b
</span><a href="#local-6989586621679171948"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171946"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-198"></span><span>
</span><span id="line-199"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679171915"><span id="local-6989586621679171917"><span id="local-6989586621679171919"><span id="local-6989586621679171921"><span id="local-6989586621679171923"><span id="local-6989586621679171925"><span id="local-6989586621679171929"><span id="local-6989586621679171931"><span id="local-6989586621679171933"><span id="local-6989586621679171935"><span id="local-6989586621679171937"><span id="local-6989586621679171939"><span id="local-6989586621679171941"><span id="local-6989586621679171944"><span class="annot"><a href="../../base/src/Data.Foldable.html#Foldable"><span class="hs-identifier hs-type">Foldable</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-200"></span><span>    </span><span id="local-6989586621679171906"><span class="annot"><span class="annottext">foldMap :: forall m a. Monoid m =&gt; (a -&gt; m) -&gt; Tree a -&gt; m
</span><a href="../../base/src/Data.Foldable.html#foldMap"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldMap</span></a></span></span><span> </span><span id="local-6989586621679171904"><span class="annot"><span class="annottext">a -&gt; m
</span><a href="#local-6989586621679171904"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171903"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171903"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171902"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171902"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; m
</span><a href="#local-6989586621679171904"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171903"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">m -&gt; m -&gt; m
forall a. Monoid a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Base.html#mappend"><span class="hs-operator hs-var">`mappend`</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; m) -&gt; [Tree a] -&gt; m
forall (t :: * -&gt; *) m a.
(Foldable t, Monoid m) =&gt;
(a -&gt; m) -&gt; t a -&gt; m
</span><a href="../../base/src/Data.Foldable.html#foldMap"><span class="hs-identifier hs-var">foldMap</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; m) -&gt; Tree a -&gt; m
forall (t :: * -&gt; *) m a.
(Foldable t, Monoid m) =&gt;
(a -&gt; m) -&gt; t a -&gt; m
</span><a href="../../base/src/Data.Foldable.html#foldMap"><span class="hs-identifier hs-var">foldMap</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; m
</span><a href="#local-6989586621679171904"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171902"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-cpp">

#if MIN_VERSION_base(4,8,0)
</span><span>    </span><span id="local-6989586621679171901"><span class="annot"><span class="annottext">null :: forall a. Tree a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var hs-var hs-var hs-var">null</span></a></span></span><span> </span><span class="annot"><span class="annottext">Tree a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Bool
</span><span class="hs-identifier hs-var">False</span></span><span>
</span><span id="line-204"></span><span>    </span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#null"><span class="hs-pragma hs-type">null</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-205"></span><span>    </span><span id="local-6989586621679171899"><span class="annot"><span class="annottext">toList :: forall a. Tree a -&gt; [a]
</span><a href="#local-6989586621679171899"><span class="hs-identifier hs-var hs-var hs-var hs-var">toList</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [a]
forall a. Tree a -&gt; [a]
</span><a href="Data.Tree.html#flatten"><span class="hs-identifier hs-var">flatten</span></a></span><span>
</span><span id="line-206"></span><span>    </span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#toList"><span class="hs-pragma hs-type">toList</span></a></span><span> </span><span class="hs-pragma">#-}</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-209"></span><span id="local-6989586621679172465"><span class="hs-keyword">instance</span><span> </span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier hs-type">NFData</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172465"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier hs-type">NFData</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172465"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-210"></span><span>    </span><span id="local-6989586621679171890"><span class="annot"><span class="annottext">rnf :: Tree a -&gt; ()
</span><a href="#local-6989586621679171890"><span class="hs-identifier hs-var hs-var hs-var hs-var">rnf</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171889"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171889"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171888"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171888"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; ()
forall a. NFData a =&gt; a -&gt; ()
</span><a href="../../deepseq/src/Control.DeepSeq.html#rnf"><span class="hs-identifier hs-var">rnf</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171889"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">() -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">[Tree a] -&gt; ()
forall a. NFData a =&gt; a -&gt; ()
</span><a href="../../deepseq/src/Control.DeepSeq.html#rnf"><span class="hs-identifier hs-var">rnf</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171888"><span class="hs-identifier hs-var">ts</span></a></span></span><span>
</span><span id="line-211"></span><span>
</span><span id="line-212"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679171884"><span class="annot"><a href="../../base/src/Control.Monad.Zip.html#MonadZip"><span class="hs-identifier hs-type">MonadZip</span></a></span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-213"></span><span>  </span><span id="local-6989586621679171877"><span class="annot"><span class="annottext">mzipWith :: forall a b c. (a -&gt; b -&gt; c) -&gt; Tree a -&gt; Tree b -&gt; Tree c
</span><a href="../../base/src/Control.Monad.Zip.html#mzipWith"><span class="hs-identifier hs-var hs-var hs-var hs-var">mzipWith</span></a></span></span><span> </span><span id="local-6989586621679171875"><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679171875"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171874"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171874"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679171873"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171873"><span class="hs-keyword hs-var">as</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171872"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171872"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span id="local-6989586621679171871"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171871"><span class="hs-identifier hs-var">bs</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-214"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">c -&gt; [Tree c] -&gt; Tree c
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679171875"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171874"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171872"><span class="hs-identifier hs-var">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; Tree b -&gt; Tree c) -&gt; [Tree a] -&gt; [Tree b] -&gt; [Tree c]
forall (m :: * -&gt; *) a b c.
MonadZip m =&gt;
(a -&gt; b -&gt; c) -&gt; m a -&gt; m b -&gt; m c
</span><a href="../../base/src/Control.Monad.Zip.html#mzipWith"><span class="hs-identifier hs-var">mzipWith</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; b -&gt; c) -&gt; Tree a -&gt; Tree b -&gt; Tree c
forall (m :: * -&gt; *) a b c.
MonadZip m =&gt;
(a -&gt; b -&gt; c) -&gt; m a -&gt; m b -&gt; m c
</span><a href="../../base/src/Control.Monad.Zip.html#mzipWith"><span class="hs-identifier hs-var">mzipWith</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; c
</span><a href="#local-6989586621679171875"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171873"><span class="hs-keyword hs-var">as</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171871"><span class="hs-identifier hs-var">bs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-215"></span><span>
</span><span id="line-216"></span><span>  </span><span id="local-6989586621679171870"><span class="annot"><span class="annottext">munzip :: forall a b. Tree (a, b) -&gt; (Tree a, Tree b)
</span><a href="../../base/src/Control.Monad.Zip.html#munzip"><span class="hs-identifier hs-var hs-var hs-var hs-var">munzip</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171868"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171868"><span class="hs-identifier hs-var">a</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171867"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171867"><span class="hs-identifier hs-var">b</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171866"><span class="annot"><span class="annottext">[Tree (a, b)]
</span><a href="#local-6989586621679171866"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171868"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171865"><span class="hs-keyword hs-var">as</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">b -&gt; [Tree b] -&gt; Tree b
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171867"><span class="hs-identifier hs-var">b</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171864"><span class="hs-identifier hs-var">bs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-217"></span><span>    </span><span class="hs-keyword">where</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171865"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171865"><span class="hs-keyword hs-var">as</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171864"><span class="annot"><span class="annottext">[Tree b]
</span><a href="#local-6989586621679171864"><span class="hs-identifier hs-var">bs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[(Tree a, Tree b)] -&gt; ([Tree a], [Tree b])
forall (m :: * -&gt; *) a b. MonadZip m =&gt; m (a, b) -&gt; (m a, m b)
</span><a href="../../base/src/Control.Monad.Zip.html#munzip"><span class="hs-identifier hs-var">munzip</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree (a, b) -&gt; (Tree a, Tree b))
-&gt; [Tree (a, b)] -&gt; [(Tree a, Tree b)]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree (a, b) -&gt; (Tree a, Tree b)
forall (m :: * -&gt; *) a b. MonadZip m =&gt; m (a, b) -&gt; (m a, m b)
</span><a href="../../base/src/Control.Monad.Zip.html#munzip"><span class="hs-identifier hs-var">munzip</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree (a, b)]
</span><a href="#local-6989586621679171866"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-218"></span><span>
</span><span id="line-219"></span><span class="hs-comment">-- | 2-dimensional ASCII drawing of a tree.</span><span>
</span><span id="line-220"></span><span class="hs-comment">--</span><span>
</span><span id="line-221"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-222"></span><span class="hs-comment">--</span><span>
</span><span id="line-223"></span><span class="hs-comment">-- &gt; putStr $ drawTree $ fmap show (Node 1 [Node 2 [], Node 3 []])</span><span>
</span><span id="line-224"></span><span class="hs-comment">--</span><span>
</span><span id="line-225"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-226"></span><span class="hs-comment">-- 1</span><span>
</span><span id="line-227"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-228"></span><span class="hs-comment">-- +- 2</span><span>
</span><span id="line-229"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-230"></span><span class="hs-comment">-- `- 3</span><span>
</span><span id="line-231"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-232"></span><span class="hs-comment">--</span><span>
</span><span id="line-233"></span><span class="annot"><a href="Data.Tree.html#drawTree"><span class="hs-identifier hs-type">drawTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span>
</span><span id="line-234"></span><span id="drawTree"><span class="annot"><span class="annottext">drawTree :: Tree String -&gt; String
</span><a href="Data.Tree.html#drawTree"><span class="hs-identifier hs-var hs-var">drawTree</span></a></span></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[String] -&gt; String
</span><a href="../../base/src/Data.OldList.html#unlines"><span class="hs-identifier hs-var">unlines</span></a></span><span> </span><span class="annot"><span class="annottext">([String] -&gt; String)
-&gt; (Tree String -&gt; [String]) -&gt; Tree String -&gt; String
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Tree String -&gt; [String]
</span><a href="Data.Tree.html#draw"><span class="hs-identifier hs-var">draw</span></a></span><span>
</span><span id="line-235"></span><span>
</span><span id="line-236"></span><span class="hs-comment">-- | 2-dimensional ASCII drawing of a forest.</span><span>
</span><span id="line-237"></span><span class="hs-comment">--</span><span>
</span><span id="line-238"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-239"></span><span class="hs-comment">--</span><span>
</span><span id="line-240"></span><span class="hs-comment">-- &gt; putStr $ drawForest $ map (fmap show) [(Node 1 [Node 2 [], Node 3 []]), (Node 10 [Node 20 []])]</span><span>
</span><span id="line-241"></span><span class="hs-comment">--</span><span>
</span><span id="line-242"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-243"></span><span class="hs-comment">-- 1</span><span>
</span><span id="line-244"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-245"></span><span class="hs-comment">-- +- 2</span><span>
</span><span id="line-246"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-247"></span><span class="hs-comment">-- `- 3</span><span>
</span><span id="line-248"></span><span class="hs-comment">--</span><span>
</span><span id="line-249"></span><span class="hs-comment">-- 10</span><span>
</span><span id="line-250"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-251"></span><span class="hs-comment">-- `- 20</span><span>
</span><span id="line-252"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-253"></span><span class="hs-comment">--</span><span>
</span><span id="line-254"></span><span class="annot"><a href="Data.Tree.html#drawForest"><span class="hs-identifier hs-type">drawForest</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span>
</span><span id="line-255"></span><span id="drawForest"><span class="annot"><span class="annottext">drawForest :: [Tree String] -&gt; String
</span><a href="Data.Tree.html#drawForest"><span class="hs-identifier hs-var hs-var">drawForest</span></a></span></span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[String] -&gt; String
</span><a href="../../base/src/Data.OldList.html#unlines"><span class="hs-identifier hs-var">unlines</span></a></span><span> </span><span class="annot"><span class="annottext">([String] -&gt; String)
-&gt; ([Tree String] -&gt; [String]) -&gt; [Tree String] -&gt; String
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(Tree String -&gt; String) -&gt; [Tree String] -&gt; [String]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree String -&gt; String
</span><a href="Data.Tree.html#drawTree"><span class="hs-identifier hs-var">drawTree</span></a></span><span>
</span><span id="line-256"></span><span>
</span><span id="line-257"></span><span class="annot"><a href="Data.Tree.html#draw"><span class="hs-identifier hs-type">draw</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../base/src/GHC.Base.html#String"><span class="hs-identifier hs-type">String</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-258"></span><span id="draw"><span class="annot"><span class="annottext">draw :: Tree String -&gt; [String]
</span><a href="Data.Tree.html#draw"><span class="hs-identifier hs-var hs-var">draw</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171859"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679171859"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171858"><span class="annot"><span class="annottext">[Tree String]
</span><a href="#local-6989586621679171858"><span class="hs-identifier hs-var">ts0</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">String -&gt; [String]
</span><a href="../../base/src/Data.OldList.html#lines"><span class="hs-identifier hs-var">lines</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679171859"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">[String] -&gt; [String] -&gt; [String]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree String] -&gt; [String]
</span><a href="#local-6989586621679171856"><span class="hs-identifier hs-var">drawSubTrees</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree String]
</span><a href="#local-6989586621679171858"><span class="hs-identifier hs-var">ts0</span></a></span><span>
</span><span id="line-259"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-260"></span><span>    </span><span id="local-6989586621679171856"><span class="annot"><span class="annottext">drawSubTrees :: [Tree String] -&gt; [String]
</span><a href="#local-6989586621679171856"><span class="hs-identifier hs-var hs-var">drawSubTrees</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-261"></span><span>    </span><span class="annot"><a href="#local-6989586621679171856"><span class="hs-identifier hs-var">drawSubTrees</span></a></span><span> </span><span class="hs-special">[</span><span id="local-6989586621679171855"><span class="annot"><span class="annottext">Tree String
</span><a href="#local-6989586621679171855"><span class="hs-identifier hs-var">t</span></a></span></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-262"></span><span>        </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;|&quot;</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; [String] -&gt; [String]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; String -&gt; [String] -&gt; [String]
forall {a}. [a] -&gt; [a] -&gt; [[a]] -&gt; [[a]]
</span><a href="#local-6989586621679171854"><span class="hs-identifier hs-var">shift</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;`- &quot;</span></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;   &quot;</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree String -&gt; [String]
</span><a href="Data.Tree.html#draw"><span class="hs-identifier hs-var">draw</span></a></span><span> </span><span class="annot"><span class="annottext">Tree String
</span><a href="#local-6989586621679171855"><span class="hs-identifier hs-var">t</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-263"></span><span>    </span><span class="annot"><a href="#local-6989586621679171856"><span class="hs-identifier hs-var">drawSubTrees</span></a></span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171853"><span class="annot"><span class="annottext">Tree String
</span><a href="#local-6989586621679171853"><span class="hs-identifier hs-var">t</span></a></span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621679171852"><span class="annot"><span class="annottext">[Tree String]
</span><a href="#local-6989586621679171852"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-264"></span><span>        </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;|&quot;</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; [String] -&gt; [String]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">String -&gt; String -&gt; [String] -&gt; [String]
forall {a}. [a] -&gt; [a] -&gt; [[a]] -&gt; [[a]]
</span><a href="#local-6989586621679171854"><span class="hs-identifier hs-var">shift</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;+- &quot;</span></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;|  &quot;</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree String -&gt; [String]
</span><a href="Data.Tree.html#draw"><span class="hs-identifier hs-var">draw</span></a></span><span> </span><span class="annot"><span class="annottext">Tree String
</span><a href="#local-6989586621679171853"><span class="hs-identifier hs-var">t</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[String] -&gt; [String] -&gt; [String]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree String] -&gt; [String]
</span><a href="#local-6989586621679171856"><span class="hs-identifier hs-var">drawSubTrees</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree String]
</span><a href="#local-6989586621679171852"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-265"></span><span>
</span><span id="line-266"></span><span>    </span><span id="local-6989586621679171854"><span class="annot"><span class="annottext">shift :: [a] -&gt; [a] -&gt; [[a]] -&gt; [[a]]
</span><a href="#local-6989586621679171854"><span class="hs-identifier hs-var hs-var">shift</span></a></span></span><span> </span><span id="local-6989586621679171851"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171851"><span class="hs-identifier hs-var">first</span></a></span></span><span> </span><span id="local-6989586621679171850"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171850"><span class="hs-identifier hs-var">other</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">([a] -&gt; [a] -&gt; [a]) -&gt; [[a]] -&gt; [[a]] -&gt; [[a]]
forall a b c. (a -&gt; b -&gt; c) -&gt; [a] -&gt; [b] -&gt; [c]
</span><a href="../../base/src/GHC.List.html#zipWith"><span class="hs-identifier hs-var">zipWith</span></a></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [a] -&gt; [a]
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">(++)</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171851"><span class="hs-identifier hs-var">first</span></a></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [[a]] -&gt; [[a]]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; [[a]]
forall a. a -&gt; [a]
</span><a href="../../base/src/GHC.List.html#repeat"><span class="hs-identifier hs-var">repeat</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171850"><span class="hs-identifier hs-var">other</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-267"></span><span>
</span><span id="line-268"></span><span class="hs-comment">-- | Returns the elements of a tree in pre-order.</span><span>
</span><span id="line-269"></span><span class="hs-comment">--</span><span>
</span><span id="line-270"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-271"></span><span class="hs-comment">--</span><span>
</span><span id="line-272"></span><span class="hs-comment">--   a</span><span>
</span><span id="line-273"></span><span class="hs-comment">--  / \\    =&gt; [a,b,c]</span><span>
</span><span id="line-274"></span><span class="hs-comment">-- b   c</span><span>
</span><span id="line-275"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-276"></span><span class="hs-comment">--</span><span>
</span><span id="line-277"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-278"></span><span class="hs-comment">--</span><span>
</span><span id="line-279"></span><span class="hs-comment">-- &gt; flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]</span><span>
</span><span id="line-280"></span><span id="local-6989586621679171848"><span class="annot"><a href="Data.Tree.html#flatten"><span class="hs-identifier hs-type">flatten</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171848"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679171848"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-281"></span><span id="flatten"><span class="annot"><span class="annottext">flatten :: forall a. Tree a -&gt; [a]
</span><a href="Data.Tree.html#flatten"><span class="hs-identifier hs-var hs-var">flatten</span></a></span></span><span> </span><span id="local-6989586621679171847"><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679171847"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [a] -&gt; [a]
forall {a}. Tree a -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679171846"><span class="hs-identifier hs-var">squish</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679171847"><span class="hs-identifier hs-var">t</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span>
</span><span id="line-282"></span><span>  </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621679171846"><span class="annot"><span class="annottext">squish :: Tree a -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679171846"><span class="hs-identifier hs-var hs-var">squish</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171844"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171844"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171843"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171843"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171842"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171842"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171844"><span class="hs-identifier hs-var">x</span></a></span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">(Tree a -&gt; [a] -&gt; [a]) -&gt; [a] -&gt; [Tree a] -&gt; [a]
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var">Prelude.foldr</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679171846"><span class="hs-identifier hs-var">squish</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679171842"><span class="hs-identifier hs-var">xs</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171843"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-283"></span><span>
</span><span id="line-284"></span><span class="hs-comment">-- | Returns the list of nodes at each level of the tree.</span><span>
</span><span id="line-285"></span><span class="hs-comment">--</span><span>
</span><span id="line-286"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-287"></span><span class="hs-comment">--</span><span>
</span><span id="line-288"></span><span class="hs-comment">--   a</span><span>
</span><span id="line-289"></span><span class="hs-comment">--  / \\    =&gt; [[a], [b,c]]</span><span>
</span><span id="line-290"></span><span class="hs-comment">-- b   c</span><span>
</span><span id="line-291"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-292"></span><span class="hs-comment">--</span><span>
</span><span id="line-293"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-294"></span><span class="hs-comment">--</span><span>
</span><span id="line-295"></span><span class="hs-comment">-- &gt; levels (Node 1 [Node 2 [], Node 3 []]) == [[1],[2,3]]</span><span>
</span><span id="line-296"></span><span class="hs-comment">--</span><span>
</span><span id="line-297"></span><span id="local-6989586621679172444"><span class="annot"><a href="Data.Tree.html#levels"><span class="hs-identifier hs-type">levels</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172444"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172444"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">]</span></span><span>
</span><span id="line-298"></span><span id="levels"><span class="annot"><span class="annottext">levels :: forall a. Tree a -&gt; [[a]]
</span><a href="Data.Tree.html#levels"><span class="hs-identifier hs-var hs-var">levels</span></a></span></span><span> </span><span id="local-6989586621679171838"><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679171838"><span class="hs-identifier hs-var">t</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-299"></span><span>    </span><span class="annot"><span class="annottext">([Tree a] -&gt; [a]) -&gt; [[Tree a]] -&gt; [[a]]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; a) -&gt; [Tree a] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; a
forall a. Tree a -&gt; a
</span><a href="Data.Tree.html#rootLabel"><span class="hs-identifier hs-var hs-var">rootLabel</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([[Tree a]] -&gt; [[a]]) -&gt; [[Tree a]] -&gt; [[a]]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span>
</span><span id="line-300"></span><span>        </span><span class="annot"><span class="annottext">([Tree a] -&gt; Bool) -&gt; [[Tree a]] -&gt; [[Tree a]]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#takeWhile"><span class="hs-identifier hs-var">takeWhile</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; ([Tree a] -&gt; Bool) -&gt; [Tree a] -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a] -&gt; Bool
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var">null</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([[Tree a]] -&gt; [[Tree a]]) -&gt; [[Tree a]] -&gt; [[Tree a]]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span>
</span><span id="line-301"></span><span>        </span><span class="annot"><span class="annottext">([Tree a] -&gt; [Tree a]) -&gt; [Tree a] -&gt; [[Tree a]]
forall a. (a -&gt; a) -&gt; a -&gt; [a]
</span><a href="../../base/src/GHC.List.html#iterate"><span class="hs-identifier hs-var">iterate</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; [Tree a]) -&gt; [Tree a] -&gt; [Tree a]
forall (t :: * -&gt; *) a b. Foldable t =&gt; (a -&gt; [b]) -&gt; t a -&gt; [b]
</span><a href="../../base/src/Data.Foldable.html#concatMap"><span class="hs-identifier hs-var">concatMap</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [Tree a]
forall a. Tree a -&gt; [Tree a]
</span><a href="Data.Tree.html#subForest"><span class="hs-identifier hs-var hs-var">subForest</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Tree a
</span><a href="#local-6989586621679171838"><span class="hs-identifier hs-var">t</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-302"></span><span>
</span><span id="line-303"></span><span class="hs-comment">-- | Fold a tree into a &quot;summary&quot; value in depth-first order.</span><span>
</span><span id="line-304"></span><span class="hs-comment">--</span><span>
</span><span id="line-305"></span><span class="hs-comment">-- For each node in the tree, apply @f@ to the @rootLabel@ and the result</span><span>
</span><span id="line-306"></span><span class="hs-comment">-- of applying @f@ to each @subForest@.</span><span>
</span><span id="line-307"></span><span class="hs-comment">--</span><span>
</span><span id="line-308"></span><span class="hs-comment">-- This is also known as the catamorphism on trees.</span><span>
</span><span id="line-309"></span><span class="hs-comment">--</span><span>
</span><span id="line-310"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-311"></span><span class="hs-comment">--</span><span>
</span><span id="line-312"></span><span class="hs-comment">-- Sum the values in a tree:</span><span>
</span><span id="line-313"></span><span class="hs-comment">--</span><span>
</span><span id="line-314"></span><span class="hs-comment">-- &gt; foldTree (\x xs -&gt; sum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 6</span><span>
</span><span id="line-315"></span><span class="hs-comment">--</span><span>
</span><span id="line-316"></span><span class="hs-comment">-- Find the maximum value in the tree:</span><span>
</span><span id="line-317"></span><span class="hs-comment">--</span><span>
</span><span id="line-318"></span><span class="hs-comment">-- &gt; foldTree (\x xs -&gt; maximum (x:xs)) (Node 1 [Node 2 [], Node 3 []]) == 3</span><span>
</span><span id="line-319"></span><span class="hs-comment">--</span><span>
</span><span id="line-320"></span><span class="hs-comment">-- Count the number of leaves in the tree:</span><span>
</span><span id="line-321"></span><span class="hs-comment">--</span><span>
</span><span id="line-322"></span><span class="hs-comment">-- &gt; foldTree (\_ xs -&gt; if null xs then 1 else sum xs) (Node 1 [Node 2 [], Node 3 []]) == 2</span><span>
</span><span id="line-323"></span><span class="hs-comment">--</span><span>
</span><span id="line-324"></span><span class="hs-comment">-- Find depth of the tree; i.e. the number of branches from the root of the tree to the furthest leaf:</span><span>
</span><span id="line-325"></span><span class="hs-comment">--</span><span>
</span><span id="line-326"></span><span class="hs-comment">-- &gt; foldTree (\_ xs -&gt; if null xs then 0 else 1 + maximum xs) (Node 1 [Node 2 [], Node 3 []]) == 1</span><span>
</span><span id="line-327"></span><span class="hs-comment">--</span><span>
</span><span id="line-328"></span><span class="hs-comment">-- You can even implement traverse using foldTree:</span><span>
</span><span id="line-329"></span><span class="hs-comment">--</span><span>
</span><span id="line-330"></span><span class="hs-comment">-- &gt; traverse' f = foldTree (\x xs -&gt; liftA2 Node (f x) (sequenceA xs))</span><span>
</span><span id="line-331"></span><span class="hs-comment">--</span><span>
</span><span id="line-332"></span><span class="hs-comment">--</span><span>
</span><span id="line-333"></span><span class="hs-comment">-- @since 0.5.8</span><span>
</span><span id="line-334"></span><span id="local-6989586621679172436"><span id="local-6989586621679172437"><span class="annot"><a href="Data.Tree.html#foldTree"><span class="hs-identifier hs-type">foldTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172437"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172436"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172436"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172437"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172436"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-335"></span><span id="foldTree"><span class="annot"><span class="annottext">foldTree :: forall a b. (a -&gt; [b] -&gt; b) -&gt; Tree a -&gt; b
</span><a href="Data.Tree.html#foldTree"><span class="hs-identifier hs-var hs-var">foldTree</span></a></span></span><span> </span><span id="local-6989586621679171833"><span class="annot"><span class="annottext">a -&gt; [b] -&gt; b
</span><a href="#local-6989586621679171833"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; b
</span><a href="#local-6989586621679171832"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-336"></span><span>    </span><span id="local-6989586621679171832"><span class="annot"><span class="annottext">go :: Tree a -&gt; b
</span><a href="#local-6989586621679171832"><span class="hs-identifier hs-var hs-var">go</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span id="local-6989586621679171831"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171831"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span id="local-6989586621679171830"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171830"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; [b] -&gt; b
</span><a href="#local-6989586621679171833"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171831"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Tree a -&gt; b) -&gt; [Tree a] -&gt; [b]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; b
</span><a href="#local-6989586621679171832"><span class="hs-identifier hs-var">go</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171830"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-337"></span><span>
</span><span id="line-338"></span><span class="hs-comment">-- | Build a (possibly infinite) tree from a seed value in breadth-first order.</span><span>
</span><span id="line-339"></span><span class="hs-comment">--</span><span>
</span><span id="line-340"></span><span class="hs-comment">-- @unfoldTree f b@ constructs a tree by starting with the tree</span><span>
</span><span id="line-341"></span><span class="hs-comment">-- @Node { rootLabel=b, subForest=[] }@ and repeatedly applying @f@ to each</span><span>
</span><span id="line-342"></span><span class="hs-comment">-- 'rootLabel' value in the tree's leaves to generate its 'subForest'.</span><span>
</span><span id="line-343"></span><span class="hs-comment">--</span><span>
</span><span id="line-344"></span><span class="hs-comment">-- For a monadic version see 'unfoldTreeM_BF'.</span><span>
</span><span id="line-345"></span><span class="hs-comment">--</span><span>
</span><span id="line-346"></span><span class="hs-comment">-- ==== __Examples__</span><span>
</span><span id="line-347"></span><span class="hs-comment">--</span><span>
</span><span id="line-348"></span><span class="hs-comment">-- Construct the tree of @Integer@s where each node has two children:</span><span>
</span><span id="line-349"></span><span class="hs-comment">-- @left = 2*x@ and @right = 2*x + 1@, where @x@ is the 'rootLabel' of the node.</span><span>
</span><span id="line-350"></span><span class="hs-comment">-- Stop when the values exceed 7.</span><span>
</span><span id="line-351"></span><span class="hs-comment">--</span><span>
</span><span id="line-352"></span><span class="hs-comment">-- &gt; let buildNode x = if 2*x + 1 &gt; 7 then (x, []) else (x, [2*x, 2*x+1])</span><span>
</span><span id="line-353"></span><span class="hs-comment">-- &gt; putStr $ drawTree $ fmap show $ unfoldTree buildNode 1</span><span>
</span><span id="line-354"></span><span class="hs-comment">--</span><span>
</span><span id="line-355"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-356"></span><span class="hs-comment">--</span><span>
</span><span id="line-357"></span><span class="hs-comment">-- 1</span><span>
</span><span id="line-358"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-359"></span><span class="hs-comment">-- +- 2</span><span>
</span><span id="line-360"></span><span class="hs-comment">-- |  |</span><span>
</span><span id="line-361"></span><span class="hs-comment">-- |  +- 4</span><span>
</span><span id="line-362"></span><span class="hs-comment">-- |  |</span><span>
</span><span id="line-363"></span><span class="hs-comment">-- |  `- 5</span><span>
</span><span id="line-364"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-365"></span><span class="hs-comment">-- `- 3</span><span>
</span><span id="line-366"></span><span class="hs-comment">--    |</span><span>
</span><span id="line-367"></span><span class="hs-comment">--    +- 6</span><span>
</span><span id="line-368"></span><span class="hs-comment">--    |</span><span>
</span><span id="line-369"></span><span class="hs-comment">--    `- 7</span><span>
</span><span id="line-370"></span><span class="hs-comment">-- @</span><span>
</span><span id="line-371"></span><span class="hs-comment">--</span><span>
</span><span id="line-372"></span><span id="local-6989586621679172432"><span id="local-6989586621679172433"><span class="annot"><a href="Data.Tree.html#unfoldTree"><span class="hs-identifier hs-type">unfoldTree</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172433"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172432"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172433"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172433"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172432"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-373"></span><span id="unfoldTree"><span class="annot"><span class="annottext">unfoldTree :: forall b a. (b -&gt; (a, [b])) -&gt; b -&gt; Tree a
</span><a href="Data.Tree.html#unfoldTree"><span class="hs-identifier hs-var hs-var">unfoldTree</span></a></span></span><span> </span><span id="local-6989586621679171829"><span class="annot"><span class="annottext">b -&gt; (a, [b])
</span><a href="#local-6989586621679171829"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171828"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171828"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">let</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171827"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171827"><span class="hs-identifier hs-var">a</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171826"><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171826"><span class="hs-identifier hs-var">bs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; (a, [b])
</span><a href="#local-6989586621679171829"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171828"><span class="hs-identifier hs-var">b</span></a></span><span> </span><span class="hs-keyword">in</span><span> </span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171827"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; (a, [b])) -&gt; [b] -&gt; [Tree a]
forall b a. (b -&gt; (a, [b])) -&gt; [b] -&gt; [Tree a]
</span><a href="Data.Tree.html#unfoldForest"><span class="hs-identifier hs-var">unfoldForest</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; (a, [b])
</span><a href="#local-6989586621679171829"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171826"><span class="hs-identifier hs-var">bs</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-374"></span><span>
</span><span id="line-375"></span><span class="hs-comment">-- | Build a (possibly infinite) forest from a list of seed values in</span><span>
</span><span id="line-376"></span><span class="hs-comment">-- breadth-first order.</span><span>
</span><span id="line-377"></span><span class="hs-comment">--</span><span>
</span><span id="line-378"></span><span class="hs-comment">-- @unfoldForest f seeds@ invokes 'unfoldTree' on each seed value.</span><span>
</span><span id="line-379"></span><span class="hs-comment">--</span><span>
</span><span id="line-380"></span><span class="hs-comment">-- For a monadic version see 'unfoldForestM_BF'.</span><span>
</span><span id="line-381"></span><span class="hs-comment">--</span><span>
</span><span id="line-382"></span><span id="local-6989586621679172428"><span id="local-6989586621679172429"><span class="annot"><a href="Data.Tree.html#unfoldForest"><span class="hs-identifier hs-type">unfoldForest</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172429"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172428"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172429"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172429"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172428"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span></span><span>
</span><span id="line-383"></span><span id="unfoldForest"><span class="annot"><span class="annottext">unfoldForest :: forall b a. (b -&gt; (a, [b])) -&gt; [b] -&gt; [Tree a]
</span><a href="Data.Tree.html#unfoldForest"><span class="hs-identifier hs-var hs-var">unfoldForest</span></a></span></span><span> </span><span id="local-6989586621679171825"><span class="annot"><span class="annottext">b -&gt; (a, [b])
</span><a href="#local-6989586621679171825"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; Tree a) -&gt; [b] -&gt; [Tree a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; (a, [b])) -&gt; b -&gt; Tree a
forall b a. (b -&gt; (a, [b])) -&gt; b -&gt; Tree a
</span><a href="Data.Tree.html#unfoldTree"><span class="hs-identifier hs-var">unfoldTree</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; (a, [b])
</span><a href="#local-6989586621679171825"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-384"></span><span>
</span><span id="line-385"></span><span class="hs-comment">-- | Monadic tree builder, in depth-first order.</span><span>
</span><span id="line-386"></span><span id="local-6989586621679172423"><span id="local-6989586621679172424"><span id="local-6989586621679172425"><span class="annot"><a href="Data.Tree.html#unfoldTreeM"><span class="hs-identifier hs-type">unfoldTreeM</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172425"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172424"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172425"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172423"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172424"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172424"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172425"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172423"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-387"></span><span id="unfoldTreeM"><span class="annot"><span class="annottext">unfoldTreeM :: forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; b -&gt; m (Tree a)
</span><a href="Data.Tree.html#unfoldTreeM"><span class="hs-identifier hs-var hs-var">unfoldTreeM</span></a></span></span><span> </span><span id="local-6989586621679171819"><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171819"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171818"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171818"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-388"></span><span>    </span><span class="hs-special">(</span><span id="local-6989586621679171817"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171817"><span class="hs-identifier hs-var">a</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171816"><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171816"><span class="hs-identifier hs-var">bs</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171819"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171818"><span class="hs-identifier hs-var">b</span></a></span><span>
</span><span id="line-389"></span><span>    </span><span id="local-6989586621679171815"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171815"><span class="hs-identifier hs-var">ts</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(b -&gt; m (a, [b])) -&gt; [b] -&gt; m [Tree a]
forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; [b] -&gt; m [Tree a]
</span><a href="Data.Tree.html#unfoldForestM"><span class="hs-identifier hs-var">unfoldForestM</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171819"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171816"><span class="hs-identifier hs-var">bs</span></a></span><span>
</span><span id="line-390"></span><span>    </span><span class="annot"><span class="annottext">Tree a -&gt; m (Tree a)
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171817"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171815"><span class="hs-identifier hs-var">ts</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-391"></span><span>
</span><span id="line-392"></span><span class="hs-comment">-- | Monadic forest builder, in depth-first order</span><span>
</span><span id="line-393"></span><span id="local-6989586621679172417"><span id="local-6989586621679172418"><span id="local-6989586621679172419"><span class="annot"><a href="Data.Tree.html#unfoldForestM"><span class="hs-identifier hs-type">unfoldForestM</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172419"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172418"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172419"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172417"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172418"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172418"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172419"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172417"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-394"></span><span id="unfoldForestM"><span class="annot"><span class="annottext">unfoldForestM :: forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; [b] -&gt; m [Tree a]
</span><a href="Data.Tree.html#unfoldForestM"><span class="hs-identifier hs-var hs-var">unfoldForestM</span></a></span></span><span> </span><span id="local-6989586621679171810"><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171810"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; m (Tree a)) -&gt; [b] -&gt; m [Tree a]
forall (t :: * -&gt; *) (m :: * -&gt; *) a b.
(Traversable t, Monad m) =&gt;
(a -&gt; m b) -&gt; t a -&gt; m (t b)
</span><a href="../../base/src/Data.Traversable.html#mapM"><span class="hs-identifier hs-var">Prelude.mapM</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(b -&gt; m (a, [b])) -&gt; b -&gt; m (Tree a)
forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; b -&gt; m (Tree a)
</span><a href="Data.Tree.html#unfoldTreeM"><span class="hs-identifier hs-var">unfoldTreeM</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171810"><span class="hs-identifier hs-var">f</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-395"></span><span>
</span><span id="line-396"></span><span class="hs-comment">-- | Monadic tree builder, in breadth-first order.</span><span>
</span><span id="line-397"></span><span class="hs-comment">--</span><span>
</span><span id="line-398"></span><span class="hs-comment">-- See 'unfoldTree' for more info.</span><span>
</span><span id="line-399"></span><span class="hs-comment">--</span><span>
</span><span id="line-400"></span><span class="hs-comment">-- Implemented using an algorithm adapted from /Breadth-First Numbering: Lessons</span><span>
</span><span id="line-401"></span><span class="hs-comment">-- from a Small Exercise in Algorithm Design/, by Chris Okasaki, /ICFP'00/.</span><span>
</span><span id="line-402"></span><span id="local-6989586621679171806"><span id="local-6989586621679171807"><span id="local-6989586621679171808"><span class="annot"><a href="Data.Tree.html#unfoldTreeM_BF"><span class="hs-identifier hs-type">unfoldTreeM_BF</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171808"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171807"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171808"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171806"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679171807"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171807"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171808"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171806"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-403"></span><span id="unfoldTreeM_BF"><span class="annot"><span class="annottext">unfoldTreeM_BF :: forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; b -&gt; m (Tree a)
</span><a href="Data.Tree.html#unfoldTreeM_BF"><span class="hs-identifier hs-var hs-var">unfoldTreeM_BF</span></a></span></span><span> </span><span id="local-6989586621679171802"><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171802"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171801"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171801"><span class="hs-identifier hs-var">b</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Seq (Tree a) -&gt; Tree a) -&gt; m (Seq (Tree a)) -&gt; m (Tree a)
forall (m :: * -&gt; *) a1 r. Monad m =&gt; (a1 -&gt; r) -&gt; m a1 -&gt; m r
</span><a href="../../base/src/GHC.Base.html#liftM"><span class="hs-identifier hs-var">liftM</span></a></span><span> </span><span class="annot"><span class="annottext">Seq (Tree a) -&gt; Tree a
forall {a}. Seq a -&gt; a
</span><a href="#local-6989586621679171800"><span class="hs-identifier hs-var">getElement</span></a></span><span> </span><span class="annot"><span class="annottext">(m (Seq (Tree a)) -&gt; m (Tree a)) -&gt; m (Seq (Tree a)) -&gt; m (Tree a)
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
</span><a href="Data.Tree.html#unfoldForestQ"><span class="hs-identifier hs-var">unfoldForestQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171802"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b -&gt; Seq b
forall a. a -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#singleton"><span class="hs-identifier hs-var">singleton</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171801"><span class="hs-identifier hs-var">b</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-404"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-405"></span><span>    </span><span id="local-6989586621679171800"><span class="annot"><span class="annottext">getElement :: Seq a -&gt; a
</span><a href="#local-6989586621679171800"><span class="hs-identifier hs-var hs-var">getElement</span></a></span></span><span> </span><span id="local-6989586621679171796"><span class="annot"><span class="annottext">Seq a
</span><a href="#local-6989586621679171796"><span class="hs-identifier hs-var">xs</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Seq a -&gt; ViewL a
forall a. Seq a -&gt; ViewL a
</span><a href="Data.Sequence.Internal.html#viewl"><span class="hs-identifier hs-var">viewl</span></a></span><span> </span><span class="annot"><span class="annottext">Seq a
</span><a href="#local-6989586621679171796"><span class="hs-identifier hs-var">xs</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-406"></span><span>        </span><span id="local-6989586621679171795"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171795"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3A%3C"><span class="hs-operator hs-type">:&lt;</span></a></span><span> </span><span class="annot"><span class="annottext">Seq a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171795"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-407"></span><span>        </span><span class="annot"><span class="annottext">ViewL a
</span><a href="Data.Sequence.Internal.html#EmptyL"><span class="hs-identifier hs-var">EmptyL</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">String -&gt; a
forall a. HasCallStack =&gt; String -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;unfoldTreeM_BF&quot;</span></span><span>
</span><span id="line-408"></span><span>
</span><span id="line-409"></span><span class="hs-comment">-- | Monadic forest builder, in breadth-first order</span><span>
</span><span id="line-410"></span><span class="hs-comment">--</span><span>
</span><span id="line-411"></span><span class="hs-comment">-- See 'unfoldForest' for more info.</span><span>
</span><span id="line-412"></span><span class="hs-comment">--</span><span>
</span><span id="line-413"></span><span class="hs-comment">-- Implemented using an algorithm adapted from /Breadth-First Numbering: Lessons</span><span>
</span><span id="line-414"></span><span class="hs-comment">-- from a Small Exercise in Algorithm Design/, by Chris Okasaki, /ICFP'00/.</span><span>
</span><span id="line-415"></span><span id="local-6989586621679171789"><span id="local-6989586621679171790"><span id="local-6989586621679171791"><span class="annot"><a href="Data.Tree.html#unfoldForestM_BF"><span class="hs-identifier hs-type">unfoldForestM_BF</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171791"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171790"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171791"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679171789"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679171790"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679171790"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679171791"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">[</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679171789"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-416"></span><span id="unfoldForestM_BF"><span class="annot"><span class="annottext">unfoldForestM_BF :: forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; [b] -&gt; m [Tree a]
</span><a href="Data.Tree.html#unfoldForestM_BF"><span class="hs-identifier hs-var hs-var">unfoldForestM_BF</span></a></span></span><span> </span><span id="local-6989586621679171783"><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171783"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Seq (Tree a) -&gt; [Tree a]) -&gt; m (Seq (Tree a)) -&gt; m [Tree a]
forall (m :: * -&gt; *) a1 r. Monad m =&gt; (a1 -&gt; r) -&gt; m a1 -&gt; m r
</span><a href="../../base/src/GHC.Base.html#liftM"><span class="hs-identifier hs-var">liftM</span></a></span><span> </span><span class="annot"><span class="annottext">Seq (Tree a) -&gt; [Tree a]
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; [a]
</span><a href="../../base/src/Data.Foldable.html#toList"><span class="hs-identifier hs-var">toList</span></a></span><span> </span><span class="annot"><span class="annottext">(m (Seq (Tree a)) -&gt; m [Tree a])
-&gt; ([b] -&gt; m (Seq (Tree a))) -&gt; [b] -&gt; m [Tree a]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
</span><a href="Data.Tree.html#unfoldForestQ"><span class="hs-identifier hs-var">unfoldForestQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171783"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">(Seq b -&gt; m (Seq (Tree a)))
-&gt; ([b] -&gt; Seq b) -&gt; [b] -&gt; m (Seq (Tree a))
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[b] -&gt; Seq b
forall a. [a] -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#fromList"><span class="hs-identifier hs-var">fromList</span></a></span><span>
</span><span id="line-417"></span><span>
</span><span id="line-418"></span><span class="hs-comment">-- Takes a sequence (queue) of seeds and produces a sequence (reversed queue) of</span><span>
</span><span id="line-419"></span><span class="hs-comment">-- trees of the same length.</span><span>
</span><span id="line-420"></span><span id="local-6989586621679172403"><span id="local-6989586621679172404"><span id="local-6989586621679172405"><span class="annot"><a href="Data.Tree.html#unfoldForestQ"><span class="hs-identifier hs-type">unfoldForestQ</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier hs-type">Monad</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172405"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172404"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172405"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679172403"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172404"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172404"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679172405"><span class="hs-identifier hs-type">m</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Tree.html#Tree"><span class="hs-identifier hs-type">Tree</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172403"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span></span></span></span><span>
</span><span id="line-421"></span><span id="unfoldForestQ"><span class="annot"><span class="annottext">unfoldForestQ :: forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
</span><a href="Data.Tree.html#unfoldForestQ"><span class="hs-identifier hs-var hs-var">unfoldForestQ</span></a></span></span><span> </span><span id="local-6989586621679171775"><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171775"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679171774"><span class="annot"><span class="annottext">Seq b
</span><a href="#local-6989586621679171774"><span class="hs-identifier hs-var">aQ</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Seq b -&gt; ViewL b
forall a. Seq a -&gt; ViewL a
</span><a href="Data.Sequence.Internal.html#viewl"><span class="hs-identifier hs-var">viewl</span></a></span><span> </span><span class="annot"><span class="annottext">Seq b
</span><a href="#local-6989586621679171774"><span class="hs-identifier hs-var">aQ</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-422"></span><span>    </span><span class="annot"><span class="annottext">ViewL b
</span><a href="Data.Sequence.Internal.html#EmptyL"><span class="hs-identifier hs-var">EmptyL</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Seq (Tree a) -&gt; m (Seq (Tree a))
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="annot"><span class="annottext">Seq (Tree a)
forall a. Seq a
</span><a href="Data.Sequence.Internal.html#empty"><span class="hs-identifier hs-var">empty</span></a></span><span>
</span><span id="line-423"></span><span>    </span><span id="local-6989586621679171773"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171773"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3A%3C"><span class="hs-operator hs-type">:&lt;</span></a></span><span> </span><span id="local-6989586621679171772"><span class="annot"><span class="annottext">Seq b
</span><a href="#local-6989586621679171772"><span class="hs-identifier hs-var">aQ'</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-424"></span><span>        </span><span class="hs-special">(</span><span id="local-6989586621679171771"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171771"><span class="hs-identifier hs-var">b</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171770"><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171770"><span class="hs-keyword hs-var">as</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171775"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679171773"><span class="hs-identifier hs-var">a</span></a></span><span>
</span><span id="line-425"></span><span>        </span><span id="local-6989586621679171769"><span class="annot"><span class="annottext">Seq (Tree a)
</span><a href="#local-6989586621679171769"><span class="hs-identifier hs-var">tQ</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
forall (m :: * -&gt; *) b a.
Monad m =&gt;
(b -&gt; m (a, [b])) -&gt; Seq b -&gt; m (Seq (Tree a))
</span><a href="Data.Tree.html#unfoldForestQ"><span class="hs-identifier hs-var">unfoldForestQ</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; m (a, [b])
</span><a href="#local-6989586621679171775"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Seq b -&gt; b -&gt; Seq b) -&gt; Seq b -&gt; [b] -&gt; Seq b
forall (t :: * -&gt; *) b a.
Foldable t =&gt;
(b -&gt; a -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl"><span class="hs-identifier hs-var">Prelude.foldl</span></a></span><span> </span><span class="annot"><span class="annottext">Seq b -&gt; b -&gt; Seq b
forall a. Seq a -&gt; a -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#%7C%3E"><span class="hs-operator hs-var">(|&gt;)</span></a></span><span> </span><span class="annot"><span class="annottext">Seq b
</span><a href="#local-6989586621679171772"><span class="hs-identifier hs-var">aQ'</span></a></span><span> </span><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171770"><span class="hs-keyword hs-var">as</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-426"></span><span>        </span><span class="hs-keyword">let</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679171767"><span class="annot"><span class="annottext">Seq (Tree a)
</span><a href="#local-6989586621679171767"><span class="hs-identifier hs-var">tQ'</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679171766"><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171766"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Tree a] -&gt; [b] -&gt; Seq (Tree a) -&gt; (Seq (Tree a), [Tree a])
forall a' b'. [a'] -&gt; [b'] -&gt; Seq a' -&gt; (Seq a', [a'])
</span><a href="#local-6989586621679171765"><span class="hs-identifier hs-var">splitOnto</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span class="annot"><span class="annottext">[b]
</span><a href="#local-6989586621679171770"><span class="hs-keyword hs-var">as</span></a></span><span> </span><span class="annot"><span class="annottext">Seq (Tree a)
</span><a href="#local-6989586621679171769"><span class="hs-identifier hs-var">tQ</span></a></span><span>
</span><span id="line-427"></span><span>        </span><span class="annot"><span class="annottext">Seq (Tree a) -&gt; m (Seq (Tree a))
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; [Tree a] -&gt; Tree a
forall a. a -&gt; [Tree a] -&gt; Tree a
</span><a href="Data.Tree.html#Node"><span class="hs-identifier hs-var">Node</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679171771"><span class="hs-identifier hs-var">b</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree a]
</span><a href="#local-6989586621679171766"><span class="hs-identifier hs-var">ts</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; Seq (Tree a) -&gt; Seq (Tree a)
forall a. a -&gt; Seq a -&gt; Seq a
</span><a href="Data.Sequence.Internal.html#%3C%7C"><span class="hs-operator hs-var">&lt;|</span></a></span><span> </span><span class="annot"><span class="annottext">Seq (Tree a)
</span><a href="#local-6989586621679171767"><span class="hs-identifier hs-var">tQ'</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-428"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-429"></span><span>    </span><span id="local-6989586621679172386"><span id="local-6989586621679172387"><span class="annot"><a href="#local-6989586621679171765"><span class="hs-identifier hs-type">splitOnto</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172387"><span class="hs-identifier hs-type">a'</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172386"><span class="hs-identifier hs-type">b'</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172387"><span class="hs-identifier hs-type">a'</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier hs-type">Seq</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679172387"><span class="hs-identifier hs-type">a'</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679172387"><span class="hs-identifier hs-type">a'</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span></span></span><span>
</span><span id="line-430"></span><span>    </span><span id="local-6989586621679171765"><span class="annot"><span class="annottext">splitOnto :: forall a' b'. [a'] -&gt; [b'] -&gt; Seq a' -&gt; (Seq a', [a'])
</span><a href="#local-6989586621679171765"><span class="hs-identifier hs-var hs-var">splitOnto</span></a></span></span><span> </span><span id="local-6989586621679171762"><span class="annot"><span class="annottext">[a']
</span><a href="#local-6989586621679171762"><span class="hs-keyword hs-var">as</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span> </span><span id="local-6989586621679171761"><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171761"><span class="hs-identifier hs-var">q</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171761"><span class="hs-identifier hs-var">q</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">[a']
</span><a href="#local-6989586621679171762"><span class="hs-keyword hs-var">as</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-431"></span><span>    </span><span class="annot"><a href="#local-6989586621679171765"><span class="hs-identifier hs-var">splitOnto</span></a></span><span> </span><span id="local-6989586621679171760"><span class="annot"><span class="annottext">[a']
</span><a href="#local-6989586621679171760"><span class="hs-keyword hs-var">as</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">b'
</span><span class="hs-identifier">_</span></span><span class="annot"><span class="hs-glyph hs-type">:</span></span><span id="local-6989586621679171759"><span class="annot"><span class="annottext">[b']
</span><a href="#local-6989586621679171759"><span class="hs-identifier hs-var">bs</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679171758"><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171758"><span class="hs-identifier hs-var">q</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">case</span><span> </span><span class="annot"><span class="annottext">Seq a' -&gt; ViewR a'
forall a. Seq a -&gt; ViewR a
</span><a href="Data.Sequence.Internal.html#viewr"><span class="hs-identifier hs-var">viewr</span></a></span><span> </span><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171758"><span class="hs-identifier hs-var">q</span></a></span><span> </span><span class="hs-keyword">of</span><span>
</span><span id="line-432"></span><span>        </span><span id="local-6989586621679171757"><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171757"><span class="hs-identifier hs-var">q'</span></a></span></span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3A%3E"><span class="hs-operator hs-type">:&gt;</span></a></span><span> </span><span id="local-6989586621679171755"><span class="annot"><span class="annottext">a'
</span><a href="#local-6989586621679171755"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">[a'] -&gt; [b'] -&gt; Seq a' -&gt; (Seq a', [a'])
forall a' b'. [a'] -&gt; [b'] -&gt; Seq a' -&gt; (Seq a', [a'])
</span><a href="#local-6989586621679171765"><span class="hs-identifier hs-var">splitOnto</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a'
</span><a href="#local-6989586621679171755"><span class="hs-identifier hs-var">a</span></a></span><span class="annot"><span class="annottext">a' -&gt; [a'] -&gt; [a']
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span class="annot"><span class="annottext">[a']
</span><a href="#local-6989586621679171760"><span class="hs-keyword hs-var">as</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[b']
</span><a href="#local-6989586621679171759"><span class="hs-identifier hs-var">bs</span></a></span><span> </span><span class="annot"><span class="annottext">Seq a'
</span><a href="#local-6989586621679171757"><span class="hs-identifier hs-var">q'</span></a></span><span>
</span><span id="line-433"></span><span>        </span><span class="annot"><span class="annottext">ViewR a'
</span><a href="Data.Sequence.Internal.html#EmptyR"><span class="hs-identifier hs-var">EmptyR</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">String -&gt; (Seq a', [a'])
forall a. HasCallStack =&gt; String -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;unfoldForestQ&quot;</span></span><span>
</span><span id="line-434"></span></pre></body></html>